Ātrā Furjē transformācija un ātrā reizināšana: skats no malas

(Uzmetums)

Skats no malas (manējais) un skats no alas (profesionāļa skats).

Kādam jābūt ideālam kādas idejas izklāstam? Tādam, ko var izlasīt un saprast neprofesionālis - bez citas literatūras lasīšanas (self-contained) un bez tehnisku detaļu pārbagātības. (Lasot Knuth, rodas doma, ka tradicionālā matemātiķu valoda nav nemaz tik piemērota FFT un ātrās reizināšanas ideju un algoritmu izklāstam - neprofesionālim tās nedaudzās lpp liekas ļoti samudžinātas. Kaut gan - vairākās vietās Knuts tomēr īsi pasvītro arī galveno. Un tas, ka viņš savā ātrās reizināšanas nodaļā vēsturiskā secībā izklāsta visas idejas, sākot no Karacubas, arī liecina viņam par labu.) [Vēl par Zeilbergera ideju, ka tradicionālā "cilvēku matemātikas" valoda nav līdz galam piemērota reālo diskrēto struktūru analīzei...]

Reizinot divus n-zīmīgus skaitļus decimālajā vai binārājā pierakstā (piemēru!) ar parasto skolas metodi, ir jāveic (ar kārtu) n2 elementāro operāciju (reizināšanu un saskaitīšanu). Vai nevar ātrāk? Kāpēc tāds jautājums? Tāpēc, ka minētājās elementārajās operācijās operandi daudzās vietās atkārtojas! Tas nozīmē, ka, procesu labāk organizējot, te būtu iespējams kaut ko ietaupīt, un n2 operāciju vietā iegūt kaut ko mazāku. Cik mazu? Beigās redzēsim, ka sanāk pat O(n log n loglog n).

Pirmo ideju ieteica Anatolijs Karacuba 1962.gadā.

 

 

Klasiķi:

Karatsuba Anatolii Alexeevich, 1962

Andrei Toom, 1963

Arnold Schönhage (born 1934)

Volker Strassen

http://homepage.mac.com/redbird/iblog/G-Squared/C1515124790/E1534009371/

 

Furjē transformācija (teksts ar Guntas ieteiktajiem uzlabojumiem)

Tagad laikam nav svarīgi, kā šī konstrukcija radusies - no skaņas viļņu analīzes vai kā citādi. Runa ir par specifisku un diezgan sarežģītu operāciju, kas jebkurus n skaitļus pārveido par citiem n skaitļiem, un kurai sākotnējo vienkāršo O(n2) algoritmu var aizstāt viltīgāks O(n log n) algoritms. Cilvēkam no malas Furjē transformācija neliekas sevišķi "sakarīgs" uzdevums. Bet izrādās, ka ar šīs operācijas palīdzību var realizēt citas - jau "sakarīgas" operācijas - matricu reizināšanu, skaitļu reizināšanu u.c. Tādā veidā arī šīm "sakarīgajām" operācijām izdodas uzbūvēt daudz ātrākus algoritmus!

Sākotnēji Furjē transformācijas tika aplūkotas kompleksajiem skaitļiem. Bet to lietojamībai nav nepieciešamas visas komplekso skaitļu īpašības. Pietiek zināt, ka mums ir darīšana ar jebkuru komutatīvu gredzenu ar vieninieku, t.i., ar jebkuru "normālu skaitļu sistēmu", kurā ir saskaitīšana, atņemšana un reizināšana, bet nav garantēta dalīšanas iespēja. T.i., precīzāk - ar algebrisku sistēmu, kurā ir asociatīva un komutatīva saskaitīšana, ir nulle un atņemšana, ir asociatīva un komutatīva reizināšana, kas ir distributīva pret saskaitīšanu, ir vieninieks (bet dalīšanas operācija nav garantēta). Gredzena elementus sauksim par skaitļiem.

Neparastāka gredzena piemērs. Aplūkosim veselos skaitļus pēc moduļa n. Pēc moduļa n šie skaitļi sadalās n klasēs, pie tam i-tajai klasei K[i] pieder visi skaitļi, kas dalot ar n, dod atlikumu i (šeit i mainās no 0 līdz n-1). Klases K[0], K[1], ..., K[n-1] veido komutatīvu gredzenu ar vieninieku, ja klašu saskaitīšanu un reizināšanu definē, balstoties uz caur veselo skaitļu saskaitīšanu un reizināšanu: paņem no katras klases pa skaitlim, saskaita tos vai sareizina, un tad atrod klasi, kurai pieder rezultāts.

Piemēram, ja n=4, tad K[2]+K[3]=K[1]. Tiešām, no K[2] ņemam skaitli 2 (vai 14), no K[3] - skaitli 3 (vai 7), 2+3=5 (vai 14+7=21), rezultāts 5 (tāpat kā 21) pieder klasei K[1].

Nav grūti parādīt, ka operācijas rezultāts nav atkarīgs no skaitļu izvēles, bet tikai no tā, kurām klasēm skaitļi pieder, un ka nulles lomu spēlē klase K[0], bet vieninieka lomu - klase K[1]. Gredzena piemēra beigas.

Pieņemsim, ka mūsu gredzenā eksistē primitīva n-tās pakāpes sakne no 1, t.i. tāds skaitlis w, ka wn=1, bet starp skaitļiem w0, w1, ..., wn-1 nav divu vienādu (protams, w0=1).

Tad par Furjē transformāciju (FT) sauc īpašu attēlojumu Fn(w), kas katrus n skaitļus (u0, u1, ..., un-1) pārveido par citiem n skaitļiem (v0, v1, ..., vn-1):

vi = SUM(j=0..n-1)wijuj.

Piemērs. Pieņemsim, ka n=4. Tad Furjē transformācija F4(w) katru skaitļu četrinieku (u0, u1, u2, u3) pārveido par citu skaitļu četrinieku (v0, v1, v2, v3):

v0 = u0+u1+u2+u3;
v1 = u0+w1u1+w2u2+w3u3;
v2 = u0+w2u1+w4u2+w6u3;
v3 = u0+w3u1+w6u2+w9u3;

jeb:

v0   w0 w0 w0 w0   u0
v1   w0 w1 w2 w3   u1
v2   w0 w2 w4 w6   u2
v3   w0 w3 w6 w9   u3

Ar šo bildi ir domāta vektora reizināšana ar matricu, t.i. lineāra transformācija (labajā pusē ir vektors, vidū - matrica, bet kreisajā pusē - rezultāts). Varētu likties, ka (v0, v1, v2, v3) aprēķināšanai vajadzīgs izpildīt 42=16 skaitļu reizināšanas un 4(4-1)=12 saskaitīšanas.

Vispārīgajā gadījumā liekas, ka Furjē transformācijas Fn(w) izpildei vajadzīgas O(n2) skaitļu reizināšanas un saskaitīšanas operācijas. Bet izrādās, ka var izgudrot labāku algoritmsu kura izpildei būs vajadzīgas tikai O(n log n) operācijas.

Problēma. FT ir piemērs šķietami O(n2) uzdevumam, kuru uzlabots algoritms spēj atrisināt O(n log n) laikā. Vai ir vēl citi uzdevumi ar šo pašu īpašību, ko varētu izmantot FT vietā?

Izšķirošā ideja: F2k(w) var viegli reducēt uz divām Fk(w2). Nva grūti parādīt, ka ja w ir primitīva 2k-tās pakāpes sakne no 1, tad w2 ir primitīva k-tās pakāpes sakne no1.)

Tātad pieņemsim, ka n=2k. Izrādās, ka vi rēķināšana, kad i ir pāru skaitlis vai nepāra skaitlis, stipri atšķiras.

Pirmkārt, pāra indeksiem 2i, kur i=0..k-1:

v2i = SUM(j=0..2k-1)w2ijuj = SUM(j=0..k-1)(w2)ijuj + SUM(j=k..2k-1)(w2)ijuj =
SUM(j=0..k-1)(w2)ijuj + SUM(j=0..k-1)(w2)i(j+k)uj+k = (otrajā summā j aizstājam ar j+k)
/*SUM(j=k-k..2k-1-k)(w2)i(j+k)uj+k = SUM(j=0..k-1)(w2)i(j+k)uj+k */
SUM(j=0..k-1)(w2)ijuj + SUM(j=0..k-1)(w2)ijuj+k = (jo w2ik=w2k=1)
/* 2i(j+k) = 2ij + 2ik; (w2)i(j+k) = (w2)ij*w2ik; w2ik = 1*/
SUM(j=0..k-1)(w2)ij(uj+uj+k).

Mūsu piemērā ar n=4:

v0 = u0+u1+u2+u3 = u0+u2+u1+u3;
v2 = u0+w2u1+w4u2+w6u3 = u0+u2+w2(u1+u3); (jo w4=1)

Šīs divas rindiņas var attēlot arī šādi:

v0   1 1   u0+u2
v2   1 w2   u1+u3

Ar šo bildi atkal ir domāta vektora reizināšana ar matricu. Matrica (vidū) atbilst F2(w2).

Kopsavilkums pāra indeksiem:

Lai aprēķinātu v2i visiem i=0..k-1, ir jāizpilda k saskaitīšanas uj+uj+k, pēc tam šiem k skaitļiem (j=0..k-1) vienreiz jāpielieto Fk(w2).

Otrkārt, nepāra indeksiem 2i+1, kur i=0..k-1:

v2i+1 = SUM(j=0..2k-1)w(2i+1)juj = SUM(j=0..k-1)w(2i+1)juj + SUM(j=k..2k-1)w(2i+1)juj =
SUM(j=0..k-1)(w2)ijwjuj + SUM(j=0..k-1)(w2)i(j+k)wj+kuj+k = (otrajā summā j aizstājam ar j+k)
/* (2i+1)j = 2ij+j; w(2i+1)j = (w2)ijwj; (2i+1)(j+k) = 2ij+2ik+j+k = 2i(j+k)+(j+k);
SUM(j=k-k..2k-1-k)w(2i+1)(j+k)uj+k = SUM(j=0..k-1)(w2)i(j+k)*wj+k */

SUM(j=0..k-1)(w2)ijwj(uj+wkuj+k).
/* 2i(j+k)+(j+k) = 2ij+2ik+j+k; (w2)i(j+k)wj+kuj+k = (w2)ijwj(w2ik*wk*uj+k) ; w2ik = 1 */

Mūsu piemērā ar n=4:

v1 = u0+w1u1+w2u2+w3u3 = u0+w2u2+w1(u1+w2u3);
v3 = u0+w3u1+w6u2+w9u3 = u0+w2u2+w3(u1+w2u3); jo w4=1)

Šīs divas rindiņas var attēlot arī šādi:

v1   1 1   u0+w2u2
v3   1 w2   w1u1+w3u3

un šādi:

v1   1 1   1 0   u0+w2u2
v3   1 w2   0 w1   u1+w2u3

Ar šo bildi atkal ir domāta vektora reizināšana ar matricām. Pirmā matrica atbilst F2(w2).

Kopsavilkums nepāra indeksiem:

Lai aprēķinātu v2i+1 visiem i=0..k-1, ir jāizpilda k reizināšanas wkuj+k, tad k saskaitīšanas uj+wkuj+k, un k reizināšanas wj(uj+wkuj+k), pēc tam šiem k skaitļiem (j=0..k-1) vienreiz jāpielieto Fk(w2).

Kopsavilkums:

Lai aprēķinātu F2k(w), ir jāizpilda 4k saskaitīšanas un reizināšanas, un pēc tam divreiz jāpielieto Fk(w2).

Ja ar |Fn(w)| apzīmēsim operāciju skaitu transformācijas Fn(w) izpildei, tad varam teikt, ka tikko esam pierādījuši, ka

|F2k(w)|<=4k+2|Fk(w2)|.

No tā pēc indukcijas seko, ka ja k=2t, tad |Fk(w2)|<=Ct2t, kur C ir konstante. Tiešām, ja |Fk(w2)|<=Ct2t, tad |F2k(w)|<=2t+2+2Ct2t <= C(t+1)2t+1(2/C+t)/(t+1) <= C(t+1)2t+1 (ja C>=2). Līdz ar to visām divnieka pakāpēm n:

|Fn(w)| <= O(n log n).

Cilvēkam no malas Furjē transformācija neliekas sevišķi "sakarīgs" uzdevums. Bet izrādās, ka ar šīs operācijas palīdzību var realizēt citas - jau "sakarīgas"operācijas - matricu reizināšanu, skaitļu reizināšanu u.c. Tādā veidā arī šīm "sakarīgajām" operācijām izdodas uzbūvēt daudz ātrākus algoritmus!

Pirmais solis šajā virzienā

varētu būt šāds uzdevums. Sāksim ar piemēru, kad n=4. Mums ir divi skaitļu četrinieki - (x0, x1, x2, x3) un (y0, y1, y2, y3), un mēs gribam izrēķināt 4 šādus skaitļus (z0, z1, z2, z3):

z0 = x0y0+x1y3+x2y2+x3y1;
z1 = x0y1+x1y0+x2y3+x3y2;
z2 = x0y2+x1y1+x2y0+x3y3;
z3 = x0y3+x1y2+x2y1+x3y0;

Kopā pa visām 4 rindiņām te ir visi iespējamie 16 reizinājumi xiyj, bet zk ir to reizinājumu xiyj summa, kam i+j=k(mod 4), t.i. i+j, dalot ar 4, dod atlikumu k. Lai izrēķinātu (z0, z1, z2, z3), it kā būtu vajadzīgas 16 skaitļu reizināšanas un 12 saskaitīšanas?

Protams, mēs varētu pamanīt, ka z0+z1+z2+z3 = (x0+x1+x2+x3)(y0+y1+y2+y3), un tā kaut ko ietaupīt. Bet radikālu uzlabojumu, izrādās, dod Furjē transformācija. Aplūkosim četriniekus (u0, u1, u2, u3), (v0, v1, v2, v3), kas ir attiecīgi (x0, x1, x2, x3) un (y0, y1, y2, y3) Furjē transformācijas:

u0 = x0+x1+x2+x3;
u1 = x0+w1x1+w2x2+w3x3;
u2 = x0+w2x1+w4x2+w6x3;
u3 = x0+w3x1+w6x2+w9x3;

v0 = y0+y1+y2+y3;
v1 = y0+w1y1+w2y2+w3y3;
v2 = y0+w2y1+w4y2+w6y3;
v3 = y0+w3y1+w6y2+w9y3;

Aplūkosim reizinājumu četrinieku (u0v0, u1v1, u2v2, u3v3):

u0v0 = (x0+x1+x2+x3)(y0+y1+y2+y3) = z0+z1+z2+z3;
u1v1 = SUM(i=0..3; j=0..3)xiwiyjwj = SUM(i=0..3; j=0..3)wi+jxiyj = z0+w1z1+w2z2+w3z3; (grupējam saskaitāmos pēc atlikumiem, kas rodas, dalot i+j ar 4)
u2v2 = SUM(i=0..3; j=0..3)xiw2iyjw2j = SUM(i=0..3; j=0..3)w2(i+j)xiyj = z0+w2z1+w4z2+w6z3; (grupējam saskaitāmos pēc atlikumiem, kas rodas, dalot i+j ar 4)
u3v3 = SUM(i=0..3; j=0..3)xiw3iyjw3j = SUM(i=0..3; j=0..3)w3(i+j)xiyj = z0+w3z1+w6z2+w9z3; (grupējam saskaitāmos pēc atlikumiem, kas rodas, dalot i+j ar 4)

Secinājums: reizinājumu četrinieks (u0v0, u1v1, u2v2, u3v3) ir četrinieka (z0, z1, z2, z3) Furjē transformācija.

Šo secinājumu nav grūti vispārināt patvaļīgam n:

s=0..n-1;
zs = SUM(i=0..n-1; j=0..n-1; i+j=s mod n) xiyj;

k=0..n-1;
ukvk = SUM(i=0..n-1; j=0..n-1)xiwkiyjwkj = SUM(i=0..n-1; j=0..n-1)wk(i+j)xiyj =
SUM(s=0..n-1) wkszs; (grupējam saskaitāmos pēc atlikumiem, kas rodas, dalot i+j ar n)

Secinājums: reizinājumu vektors (u0v0, u1v1, ..., un-1vn-1) ir vektora (z0, z1, ..., zn-1) Furjē transformācija.

Secinājums: lai izrēķinātu vektora (z0, z1, ..., zn-1) Furjē transformāciju, ir jāizrēķina divas Frujē transformācijas - attiecīgi vektoram (x0, x1, ..., xn-1) un vektoram (y0, y1, ..., yn-1), un rezultātu koordinātes pa pāriem jāsareizina. Pavisam tātad būs vajadzīgas

O(n log n) + O(n log n) + n = O(n log n)

operācijas.

Bet mēs taču gribējām izēķināt pašu vektoru (z0, z1, ..., zn-1), nevis tā Furjē transformāciju?

 

Lemma. SUM(i=0..n-1)wi = 0. Pie n=2: 1+w=0, pie n=3: 1+w+w2=0, utt.

Secinājums. SUM(i=0..n-1)ui = nx0.

Otrais solis

Reizinot divus 4-zīmju skaitļus binārājā sistēmā, vispirms veidojas šāda aina:

        a3 a2 a1 a0
        b3 b2 b1 b0
        a3b0 a2b0 a1b0 a0b0
      a3b1 a2b1 a1b1 a0b1  
    a3b2 a2b2 a1b2 a0b2    
  a3b3 a2b3 a1b3 a0b3      
c7 c6 c5 c4 c3 c2 c1 c0

Pēc tam, reizinājumi ir jāsummē pa kolonām. Ko mēs te redzam? Numurējot kolonas no labās puses uz kreiso (un sākot ar 0), k-tajā kolonā tiek summēti tie reizinājumi aibj, kam i+j=k. Tieši tos pašus rezinājumus mēs varam ieraudzīt savā "pirmā soļa" tabulā pie n=8 (k-tajā rindā ir tie reizinājumi aibj, kam i+j=k(mod 8), t.i. i+j, dalot ar 8, dod atlikumu k):

c0 a0b0 a1b7 a2b6 a3b5 a4b4 a5b3 a6b2 a7b1
c1 a0b1 a1b0 a2b7 a3b6 a4b5 a5b4 a6b3 a7b2
c2 a0b2 a1b1 a2b0 a3b7 a4b6 a5b5 a6b4 a7b3
c3 a0b3 a1b2 a2b1 a3b0 a4b7 a5b6 a6b5 a7b4
c4 a0b4 a1b3 a2b2 a3b1 a4b0 a5b7 a6b6 a7b5
c5 a0b5 a1b4 a2b3 a3b2 a4b1 a5b0 a6b7 a7b6
c6 a0b6 a1b5 a2b4 a3b3 a4b2 a5b1 a6b0 a7b7
c7 a0b7 a1b6 a2b5 a3b4 a4b3 a5b2 a6b1 a7b0

Tātad mūs interesējošās summas mēs varam iegūt no "pirmā soļa" vektoriem (a0, a1, a2, a3, a4, a5, a6, a7) un (b0, b1, b2, b3, b4, b5, b6, b7) pie a4 = a5 = a6 = a7 = 0 un b4 = b5 = b6 = b7 =0.

Turpinājums sekos.