Montrez comment faire la FFT à la main

27

Supposons que vous ayez deux polynômes: 3+x et 2x2+2 .

J'essaie de comprendre comment la FFT nous aide à multiplier ces deux polynômes. Cependant, je ne trouve aucun exemple élaboré. Quelqu'un peut-il me montrer comment l'algorithme FFT multiplierait ces deux polynômes. (Remarque: ces polynômes n'ont rien de spécial, mais je voulais rester simple pour le rendre plus facile à suivre.)

J'ai regardé les algorithmes en pseudocode, mais tous semblent avoir des problèmes (ne spécifiez pas ce que l'entrée devrait être, variables non définies). Et étonnamment, je ne trouve pas où quelqu'un a réellement parcouru (à la main) un exemple de multiplication de polynômes en utilisant la FFT.

lars
la source
2
Wikipedia conserve cette belle image pour la multiplication d'entiers via FFT, mais je pense qu'un pas à pas encore plus explicite pourrait être utile.
Realz Slaw

Réponses:

27

Supposons que nous utilisons les quatrièmes racines de l'unité, ce qui correspond à substituer 1,i,1,i à x . Nous utilisons également la décimation en temps plutôt que la décimation en fréquence dans l'algorithme FFT. (Nous appliquons également une opération d'inversion de bits de manière transparente.)

Afin de calculer la transformée du premier polynôme, nous commençons par écrire les coefficients:

3,1,0,0.
La transformée de Fourier des coefficients pairs 3,0 est 3,3 et des coefficients impairs 1,0 est 1,1 . (Cette transformée est juste a,ba+b,ab .) Par conséquent, la transformée du premier polynôme est
4,3+i,2,3i.
Ceci est obtenu en utilisantX0,2=E0±O0 ,X1,3=E1iO1 . (D'après le calcul du facteur twiddle).

Faisons de même pour le deuxième polynôme. Les coefficients sont

2,0,2,0.
Les coefficients pairs 2,2 transforment en 4,0 et les coefficients impairs 0,0 transforment en 0,0 . Par conséquent, la transformée du deuxième polynôme est
4,0,4,0.

On obtient la transformée de Fourier du polynôme produit en multipliant les deux transformées de Fourier ponctuellement:

16,0,8,0.
Il reste à calculer la transformée de Fourier inverse. Les coefficients pairs 16,8 transforment en inverse à 12,4 et les coefficients impairs 0,0 transforment en inverse à 0,0 . (La transformée inverse est x,y(x+y)/2,(xy)/2 ) Par conséquent, la transformée du polynôme produit est
6,2,6,2.
Elle est obtenue en utilisantX0,2=(E0±O0)/2 ,X1,3=(E1iO1)/2 . Nous avons obtenu la réponse souhaitée
(3+x)(2+2x2)=6+2x+6x2+2x3.

Yuval Filmus
la source
comment es-tu arrivé à 6,2 6, 2?
LARS
J'ai donné les formules: , X 1 , 3 = ( E 1i O 1 ) / 2 , où E 0 , E 1 ( O 1 , O 2 ) est la transformée inverse des coefficients pairs (impairs), obtenue par la formule x , y ( x + y )X0,2=(E0±O2)/2X1,3=(E1iO1)/2E0,E1O1,O2 . Veuillez revoir la réponse - tous les calculs sont là. x,y(x+y)/2,(xy)/2
Yuval Filmus
Pourquoi utilisez-vous deux fois les coefficients pairs? 3,3 -> 3,3,3,3. -> 3 + 1, 3-i, 3 + -1,3 - i?
Aage Torleif
Comment ces formules pour et X 1 , 3 s'étendent-elles à des degrés supérieurs? Les signes plus / moins continuent-ils tout simplement de basculer? Par exemple, que serait-ce pour X 0 , 2 , 4 ? X0,2X1,3X0,2,4
Bobby Lee
@BobbyLee Je vous encourage à lire de la littérature sur la FFT.
Yuval Filmus
7

Définissez les polynômes, où deg(A) = qet deg(B) = p. Le deg(C) = q + p.

Dans ce cas deg(C) = 1 + 2 = 3,.

A=3+xB=2x2+2C=AB=?

On peut facilement trouver C en temps O(n2) par multiplication par force brute des coefficients. En appliquant la FFT (et la FFT inverse), nous pourrions y parvenir en temps O(nlog(n)) . Explicitement:

  1. Convertissez la représentation du coefficient de A et B en sa représentation de valeur. Ce processus est appelé évaluation . L'exécution de Divide-and-Conquer (D&C) pour cela prendrait O(nlog(n)) temps.
  2. Multipliez les polynômes par composants dans leur représentation des valeurs. Cela renvoie la représentation de la valeur de C = A * B. Cela prend du temps O(n) .
  3. Inversez C en utilisant la FFT inverse pour obtenir C dans sa représentation de coefficient. Ce processus est appelé interpolation et prend également O(nlog(n)) temps.

En continuant, nous représentons chaque polynôme comme un vecteur dont la valeur est ses coefficients. Nous remplissons le vecteur avec des 0 jusqu'à la plus petite puissance de deux, n=2k,ndeg(C) . Ainsi n=4 . Choisir une puissance de deux nous offre un moyen d'appliquer récursivement notre algorithme de division et de conquête.

A=3+x+0x2+0x3a=[3,1,0,0]B=2+0x+2x+0x3b=[2,0,2,0]

Soit A,B la représentation de la valeur de A et B, respectivement. Notez que la FFT (Fast transformée de Fourier ) est une transformation linéaire ( plan linéaire ) et peut être représenté comme une matrice, M . Ainsi

A=MaB=Mb

We define M=Mn(ω) where ω is complex roots nth complex roots of unity. Notice n = 4, in this example. Also notice that the entry in the jth row and kth column is ωnjk . See more about the DFT matrix here

M4(w)=[111...11ω1ω2...ωn11ω2ω4...............ωjk...1ωn1ω2(n1)...ω(n1)(n1)]=[11111ωω2ω31ω2ω4ω61ω3ω6ω9]

Given the ω4=4th roots of unity, we have the ordered set equality:

{ω0,ω1,ω2,ω3,ω4,ω5,...}={1,i,1,i,1,i,...}

This can be visualized as iterating thru roots of the unit circle in the counter-clockwise direction.

Also, notice the mod n nature, i.e. ω6=ω6modn=ω2=1 and i=ω3=ω3+n

To complete step 1 (evaluation) we find A,B by performing

A=Ma=[11111ωω2ω31ω2ω4ω61ω3ω6ω9][3100]=[3+13+1ω3+ω23+ω3]=[43+i23i]B=Mb=[11111ωω2ω31ω2ω4ω61ω3ω6ω9][2020]=[2+22+2ω22+2ω42+2ω6]=[4040]

This step can be achieved using D&C algorithms (beyond the scope of this answer).

Multiply AB component-wise (step 2)

AB=[43+i23i][4040]=[16080]=C

Finally, the last step is to represent C' into coefficients. Notice

C=McM1C=M1Mcc=M1C

Notice Mn1=1nMn(ω1)1 and ωj=ωn/2+j.

Mn1=14[11111ω1ω2ω31ω2ω4ω61ω3ω6ω9]=14[11111i1i11111i1i]

ωj can be visualized as iterating thru roots of the unit circle in the clockwise direction.

{ω0,ω1,ω2,ω3,ω4,ω5,...}={1,i,1,i,1,i,...}

Also, it is true that, given the nth root of unity, the equality ωj=ωnj holds. (Do you see why?)

Then,

c=M1C=1nMn(w1)=14[11111i1i11111i1i][16080]=[(16+8)/4(168)/4(16+8)/4(168)/4]=[6262]

Thus, we get the polynomial

C=AB=6+2x+6x2+2x3
1: Inversion Formula pg 73, Algorithms by Dasgupta et. al. (C) 2006

j__gt
la source