FFT. Második nekifutás. Czirbusz Sándor ELTE IK, Komputeralgebra Tanszék október 2

TARTALOMJEGYZÉK Polinomok konvolúviója A DFT és a maradékos osztás Gyur ˝ uk ˝ FFT támogatás nélkül

FFT Második nekifutás Czirbusz Sándor ELTE IK, Komputeralgebra Tanszék

2015. október 2.

Czirbusz Sándor ELTE IK, Komputeralgebra Tanszék

FFT


P OLINOMOK KONVOLÚVIÓJA Definíció P Pn−1 j j Legyen f (x) = n−1 j=0 fj x és g(x) = j=0 gj x két R[x]-beli polinom. A két polinom konvolúviója a h = f ∗n g =

n−1 X

hk xk ∈ R[x]

k=1

polinom, ahol X

hk =

fi gj =

i+j≡ mod n

j=0)

minden 0 5 k < n esetén.


n−1 X

FFT

fj gk−j


M EGJEGYZÉSEK

Ha érthet˝o ∗n helyett ∗-ot írunk;


FFT


M EGJEGYZÉSEK

Ha érthet˝o ∗n helyett ∗-ot írunk; Ha Rn -beli vektoroknak tekintjük a polinomokat, akkor az f , g vektorok ciklikus konvolúciójáról beszélünk;


FFT


M EGJEGYZÉSEK

Ha érthet˝o ∗n helyett ∗-ot írunk; Ha Rn -beli vektoroknak tekintjük a polinomokat, akkor az f , g vektorok ciklikus konvolúciójáról beszélünk; A konvolúció nem más, mint a polinomok R[x]/ < xn − 1 > gyur ˝ ubeli ˝ szorzata, azaz f ∗n g = fg mod (xn − 1).


FFT


A KONVOLÚCIÓ ÉS A DFT

Legyen f , g ∈ R[x] két, legfeljebb n − 1-edfokú polinom.


FFT




Állítás DFTω (f ∗ g) = DFTω (f ) · DFTω (g), ahol · a koordinátánkénti szorzás.


FFT




Állítás DFTω (f ∗ g) = DFTω (f ) · DFTω (g), ahol · a koordinátánkénti szorzás. Bizonyítás Mivel f ∗ g = fg + q(xn − 1) valamilyen q ∈ R[x]-re, ezért (f ∗ g)(ω j ) = f (ω j )g(ω j ) + q(ω j )((ω j )n − 1) = f (ω j )g(ω j ) .


FFT


E GY DIAGRAM Az R[x] → Rn -be képez˝o, f -hez a ω hatványain felvett helyettesítési értékei vektorát rendel˝o leképezés homomorfizmus, R[x]/

<xn −1>

2

DFTω × DFTω

bels˝o szorzat

konvolúció R[x]/ n <x −1>


Rn × Rn

DFTω

FFT

Rn

TARTALOMJEGYZÉK Polinomok konvolúviója A DFT és a maradékos Motiváció osztás Az Gy algoritmus ur ˝ uk ˝ FFT támogatás A gyors konvolúció nélkül

B EVEZET O˝ PÉLDA Q[x] fölötti polinomok szorzása mod (xn − u). f := x3 + 1: g := 2 ∗ x3 + 3 ∗ x2 + x + 1 m := x4 − u: expand(f*g) 2x6 + 3x5 + x4 + 3x3 + 3x2 + x + 1 quo(f ∗ g, m, x,0 r0 ) 2x2 + 3x + 1 collect(expand(r), u) (2 ∗ x2 + 3 ∗ x + 1) ∗ u + 3 ∗ x3 + 3 ∗ x2 + x + 1

Látszik, hogy ilyen speciális alakú modulus esetén a maradék úgy épül fel, hogy a magasabb fokú tagok együtthatói az eredeti polinom magasabb fokú együtthatói, az alacsonyabb fokszámúak pedig szintén ugyanezek az eredeti polinomból.


FFT


A PÉLDA ÁLTALÁNOSÍTÁSA

Legyen f ∈ R[x] egy legfeljebb n − 1-ed fokú polinom, ahol n = 2 páros egész, 1, ω, . . . , ω n−1 pedig az ω n-edik primitív egységgyöknek megfelel˝o Fourier-pontok.


FFT



Legyen f ∈ R[x] egy legfeljebb n − 1-ed fokú polinom, ahol n = 2 páros egész, 1, ω, . . . , ω n−1 pedig az ω n-edik primitív egységgyöknek megfelel˝o n n Fourier-pontok. Osszuk el f -et maradékosan x /2 − 1-el és x /2 + 1-el. n

n

f = q0 · (x /2 − 1) + r0 = q1 · (x /2 + 1) + r1 , ahol az q0 , q1 , r0 , r1 R[x] polinomok n2 -nél kisebb fokszámúak.


FFT

(1)




n

f = q0 · (x /2 − 1) + r0 = q1 · (x /2 + 1) + r1 , ahol az q0 , q1 , r0 , r1 R[x] polinomok n2 -nél kisebb fokszámúak. Ugyanakkor n f = F1 x /2 + F0 alakban írható, ahol az F0 , F1 ∈ R[x] polinomok fokszáma szintén kisebb n2 -nél.


FFT

(1)




n

f = q0 · (x /2 − 1) + r0 = q1 · (x /2 + 1) + r1 ,

(1)

ahol az q0 , q1 , r0 , r1 R[x] polinomok n2 -nél kisebb fokszámúak. Ugyanakkor n f = F1 x /2 + F0 alakban írható, ahol az F0 , F1 ∈ R[x] polinomok fokszáma n szintén kisebb n2 -nél.Ebb˝ol F1 (x /2 − 1) = f − F0 − F1 , ezért n (x /2 − 1) | f − F0 − F1 , a maradékos osztás egyértelmusége ˝ miatt r0 = F0 + F1 .


FFT




n

f = q0 · (x /2 − 1) + r0 = q1 · (x /2 + 1) + r1 ,

(1)

ahol az q0 , q1 , r0 , r1 R[x] polinomok n2 -nél kisebb fokszámúak. Ugyanakkor n f = F1 x /2 + F0 alakban írható, ahol az F0 , F1 ∈ R[x] polinomok fokszáma n szintén kisebb n2 -nél.Ebb˝ol F1 (x /2 − 1) = f − F0 − F1 , ezért n (x /2 − 1) | f − F0 − F1 , a maradékos osztás egyértelmusége ˝ miatt r0 = F0 + F1 . Hasonlóan belátható, hogy r1 = F0 − F1. Tehát a maradék együtthatói az eredeti polinom együtthatóiból állnak, mint a fenti példában is.


FFT


K IÉRTÉKELÉS A F OURIER - PONTOKBAN Ha az (1)-be ω hatványait helyettesítjük: f (ω 2k ) = q0 (ω 2k · (ω nk − 1) + r0 (ω 2k ) = r0 (ω 2k ) , n

f (ω 2k+1 ) = q1 (ω 2k+1 · (ω nk ω /2 + 1) + r1 (ω 2k+1 ) = r1 (ω 2k+1 ) , ahol 0 5 k < n/2 .


FFT



f (ω 2k+1 ) = q1 (ω 2k+1 · (ω nk ω /2 + 1) + r1 (ω 2k+1 ) = r1 (ω 2k+1 ) , ahol 0 5 k < n/2 . Itt egyrészt azt használtuk ki, hogy ω nk = 1, másrészt a n

n

0 = (ω n − 1) = (ω /2 − 1) · (ω /2 + 1) n

n

összefüggésben (ω /2 − 1) nem lehet zérusosztó, így ω /2 = −1.


FFT



f (ω 2k+1 ) = q1 (ω 2k+1 · (ω nk ω /2 + 1) + r1 (ω 2k+1 ) = r1 (ω 2k+1 ) , ahol 0 5 k < n/2 . Itt egyrészt azt használtuk ki, hogy ω nk = 1, másrészt a n

n

0 = (ω n − 1) = (ω /2 − 1) · (ω /2 + 1) n

n

összefüggésben (ω /2 − 1) nem lehet zérusosztó, így ω /2 = −1. Vagyis az r0 -t kell kiértékelni az ω páros hatványainál, r1 -et pedig a párosaknál. Legyen r∗1 (x) = r1 (ωx). Felhasználva, hogy ω 2 n/2 -edik egységgyök, az FFT algoritmus egy „átfogalmazását” kaptuk.


FFT


A Z ALGORITMUS Algorithm 1: FFT(N, ω, a(x)) Data: Adott N, kett˝ohatvány Data: ω primitív N-edik primitív egységgyök Data: f (x) legfeljebb N − 1-ed fokú polinom Result: A polinom Fourier transzformáltja begin if N = 1 then A0 ← f0 ; else P N2 −1

i i=0 (fi + fi+N/2 ) · x ; N −1 P 2 r∗1 ← i=0 (fi − fi+N/2 ) · ω i · xi ; Az algoritmus hívása rekurzive ω 2 -el;

r0 ←

return (r0 (1), r∗1 (1), r0 (ω 2 ), r∗1 (ω 2 ), . . . , r0 (ω N−2 )), r∗1 (ω N−2 ) ;


FFT


A Z ALGORITMUS HELYESSÉGE

Tétel Legyen ω n-edik primitív egységgyök az R gyur ˝ uben, ˝ n kett˝ohatvány. Ekkor az el˝oz˝o algoritmus helyesen számolja kia DFTω -t, ehhez n log n gyur ˝ ubeli ˝ összeadásra és n/2 log n szorzásra van szükség.


FFT


A Z ALGORITMUS Algorithm 2: FastConvolution(N, ω, a(x)) Data: Adott N, kett˝ohatvány Data: ω primitív N-edik primitív egységgyök Data: f , g legfeljebb N − 1-ed fokú polinom Result: f ∗ g begin ω 2 , . . . ω N−1 kiszámítása ; α ← DFTω (f ); β ← DFTω (g) ; γ ←α·β ; // pontonkénti szorzás return DFT−1 (γ) ; ω


FFT


B ONYOLULTSÁG Definíció Azt mondjuk, hogy egy R kommutatív gyur ˝ u˝ támogatja az FFT-t, k ha R-ben minden k ∈ N esetén van 2 -adik primitív egységgyök.


FFT


B ONYOLULTSÁG Definíció Azt mondjuk, hogy egy R kommutatív gyur ˝ u˝ támogatja az FFT-t, k ha R-ben minden k ∈ N esetén van 2 -adik primitív egységgyök.

Tétel Legyen R olyan kommutatív , mely támogatja az FFT-t, n = 2k valamilyen k ∈ N-el. Legyen továbbá f , g ∈ R[x] két polinom, melyekre deg (fg) < n. Ekkor az R[x]/ < xn − 1 >-beli konvolúcióhoz 3n log n R-beli összeadás, 23 n log n + n − 2 ω-hatvánnyal való szorzás, n R-beli szorzás és n db osztás szükséges, összesen 9 ˝ Emiatt a polinomszorzás bonyolultsága 2 n log n + O(n) muvelet. 18n log n + O(n) muvelet. ˝


FFT

TARTALOMJEGYZÉK Polinomok konvolúviója A DFT és a maradékos Negative osztás wrapped Gyur ˝ uk convolution ˝ FFT támogatás nélkül

A Z ÖTLET I Legyen R olyan kommutatív gyur ˝ u, ˝ melyben a 2 egység, n = 2k , k ∈ N, valamint D = R[x]/hxn + 1i.

Állítás D-ben ω = x 2n-edik primitív egységgyök. Bizonyítás


FFT



Állítás D-ben ω = x 2n-edik primitív egységgyök. Bizonyítás Az, hogy ω = x 2n-edik egységgyök, következik az xn ≡ −1 mod (xn + 1) és x2n = (xn )2 ≡ 1 mod (xn + 1) kongruenciákból.


FFT



Állítás D-ben ω = x 2n-edik primitív egységgyök. Bizonyítás Az, hogy ω = x 2n-edik egységgyök, következik az xn ≡ −1 mod (xn + 1) és x2n = (xn )2 ≡ 1 mod (xn + 1) kongruenciákból. P Legyen p | n prím; ekkor a (c − 1) · m−1 cj = cm − 1 összefüggést j=1 n

m = p, c = ω p -re alkalmazva: n

ωp −1 =

p−1 X

n

n

(ω p )j = (ω p )p − 1 = ω n − 1 = −2

j=1

ami egység.


FFT


A Z ÖTLET II Ha f , g ∈ R[x] olyanok, hogy deg (fg) < n = 2k , akkor elegend˝o fg-t kiszámítani mod (xn + 1). (Ez a negative wrapped convolution). n

!m = 2b 2 c és t =

n m

n

= 2d 2 e . Ekkor:


FFT



n

!m = 2b 2 c és t = mn = 2d 2 e . Ekkor: P P f = 05j

FFT



n

05j
Ekkor f (x) = f 0 (x, xm ), g(x) = g0 (x, xm ).


FFT



n

05j
Ekkor f (x) = f 0 (x, xm ), g(x) = g0 (x, xm ). f 0 · g0 = h0 + q0 (yt + 1), ezért fg ≡ h0 (x, xm ) mod (xn + 1), így elegend˝o f 0 g0 mod (yt + 1)-et kiszámolni;


FFT



n

05j
Ekkor f (x) = f 0 (x, xm ), g(x) = g0 (x, xm ). f 0 · g0 = h0 + q0 (yt + 1), ezért fg ≡ h0 (x, xm ) mod (xn + 1), így elegend˝o f 0 g0 mod (yt + 1)-et kiszámolni; degy h0 < t esetén h0 egyértelmu, ˝ továbbá degx h0 < 2m.


FFT


A Z ÖTLET III

Legyen ξ = x mod x2m + 1 ∈ D = R[x]/ x2m + 1 . ξ negyedik primitív gyök;


FFT


A Z ÖTLET III

Legyen ξ = x mod x2m + 1 ∈ D = R[x]/ x2m + 1 . ξ negyedik primitív gyök; Ha most f ∗ = f 0 mod (x2m +) és hasonlóan g∗ , h∗ , akkor D[y]-ban f ∗ g∗ ≡ h∗ mod (yt + 1) ;


FFT


A Z ÖTLET III

Legyen ξ = x mod x2m + 1 ∈ D = R[x]/ x2m + 1 . ξ negyedik primitív gyök; Ha most f ∗ = f 0 mod (x2m +) és hasonlóan g∗ , h∗ , akkor D[y]-ban f ∗ g∗ ≡ h∗ mod (yt + 1) ; Mivel mindhárom polinom fokszáma kisebb, mint 2m, a mod (x2m + 1) redukció csak algebrai „néz˝opont”-váltást jelent, a struktúraváltással alkalmazható az FFT.


FFT

FFT. Második nekifutás. Czirbusz Sándor ELTE IK, Komputeralgebra Tanszék október 2

Recommend Documents