Montrez comment faire la FFT à la main

Supposons que vous ayez deux polynômes: $3 + x$ et $2x^2 + 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.

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,b \mapsto a+b,a-b$ .) Par conséquent, la transformée du premier polynôme est $$4,3+i,2,3-i.$$ Ceci est obtenu en utilisant$X_{0,2} = E_0 \pm O_0$ ,$X_{1,3} = E_1 \mp i O_1$ . (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 \mapsto (x+y)/2,(x-y)/2$ ) Par conséquent, la transformée du polynôme produit est $$6,2,6,2.$$ Elle est obtenue en utilisant$X_{0,2} = (E_0 \pm O_0)/2$ ,$X_{1,3} = (E_1 \mp i O_1)/2$ . Nous avons obtenu la réponse souhaitée $$(3 + x)(2 + 2x^2) = 6+2x+6x^2+2x^3.$$

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 + x \\ B = 2x^2 + 2 \\ C = A*B = ?$$

On peut facilement trouver C en temps $O(n^2)$ par multiplication par force brute des coefficients. En appliquant la FFT (et la FFT inverse), nous pourrions y parvenir en temps $O(n\log(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(n\log(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(n\log(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 = 2^k, n \geq deg(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.

$$\begin{align} &A = 3+x+0x^2+0x^3 \Rightarrow &\vec{a} = [3, 1, 0, 0]\\ &B = 2+0x+2x^+0x^3 \Rightarrow & \vec{b} = [2, 0, 2, 0] \end{align}$$

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' = M \overrightarrow{a} \\ B' = M \overrightarrow{b}$$

We define $M = M_n(\omega)$ where $\omega$ is complex roots $n^{th}$ complex roots of unity. Notice n = 4, in this example. Also notice that the entry in the $j^{th}$ row and $k^{th}$ column is $\omega_n^{jk}$ . See more about the DFT matrix here

$$M_4(w) = \begin{bmatrix} 1 & 1 & 1 & ... & 1\\ 1 & \omega^1 & \omega^2 & ... & \omega^{n-1}\\ 1 & \omega^2 & \omega^{4} & ... & ... \\ ... & ... & ... & \omega^{jk} & ...\\ 1 & \omega^{n-1} & \omega^{2(n-1)} & ... & \omega^{(n-1)(n-1)} \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 &1 \\ 1 &\omega & \omega^2 & \omega^3\\ 1 &\omega^2 & \omega^4 & \omega^6\\ 1 &\omega^3 & \omega^6 & \omega^9 \end{bmatrix}$$

Given the $\omega_4 = 4^{th}$ roots of unity, we have the ordered set equality:

$$\{\omega^{0},\omega^1, \omega^2, \omega^3, \omega^4, \omega^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. $\omega^6 = \omega^{6 \mod n} = \omega^{2} = -1$ and $-i = \omega^{3} = \omega^{3+n}$

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

$$A' = M * \vec{a} = \begin{bmatrix} 1 & 1 & 1 &1 \\ 1 &\omega & \omega^2 & \omega^3\\ 1 &\omega^2 & \omega^4 & \omega^6\\ 1 &\omega^3 & \omega^6 & \omega^9 \end{bmatrix} \begin{bmatrix} 3 \\ 1 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 3 + 1 \\ 3 + 1 \omega \\ 3 + \omega^2 \\ 3 + \omega^3 \end{bmatrix} = \begin{bmatrix} 4 \\ 3 + i \\ 2 \\ 3 - i \end{bmatrix} \\ B' = M * \vec{b} = \begin{bmatrix} 1 & 1 & 1 &1 \\ 1 &\omega & \omega^2 & \omega^3\\ 1 &\omega^2 & \omega^4 & \omega^6\\ 1 &\omega^3 & \omega^6 & \omega^9 \end{bmatrix} \begin{bmatrix} 2 \\ 0 \\ 2 \\ 0 \end{bmatrix} = \begin{bmatrix} 2 + 2 \\ 2 + 2 \omega^2 \\ 2 + 2\omega^4 \\ 2 + 2\omega^6 \end{bmatrix} = \begin{bmatrix} 4 \\ 0 \\ 4 \\ 0 \end{bmatrix}$$

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

Multiply $A' * B'$ component-wise (step 2)

$$A' * B' = \begin{bmatrix} 4 \\ 3 + i \\ 2 \\ 3 - i \end{bmatrix} \begin{bmatrix} 4 \\ 0 \\ 4 \\ 0 \end{bmatrix} = \begin{bmatrix} 16 \\ 0\\ 8 \\ 0 \end{bmatrix} = C'\\ $$

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

$$C' = M \vec{c} \\ \Rightarrow M^{-1}C' = M^{-1} M \vec{c} \\ \Rightarrow \vec{c} = M^{-1}C'$$

Notice $M_n^{-1} = \frac{1}{n} M_n(\omega^{-1})$¹ and $\omega^j = -\omega^{n/2 + j}$.

$$M_n^{-1} = \frac{1}{4} \begin{bmatrix} 1 & 1 & 1 &1 \\ 1 &\omega^{-1} & \omega^{-2} & \omega^{-3}\\ 1 &\omega^{-2} & \omega^{-4} & \omega^{-6}\\ 1 &\omega^{-3} & \omega^{-6} & \omega^{-9} \end{bmatrix} = \frac{1}{4} \begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & -i & -1 & i \\ 1 & -1 & 1 & -1\\ 1 & i & -1 & -i \end{bmatrix}$$

$\omega^{-j}$ can be visualized as iterating thru roots of the unit circle in the clockwise direction.

$$\{\omega^{0},\omega^{-1}, \omega^{-2}, \omega^{-3}, \omega^{-4}, \omega^{-5}, ... \} = \{1, -i, -1, i, 1, -i, ...\}$$

Also, it is true that, given the $n^{th}$ root of unity, the equality $\omega^{-j} = \omega^{n-j}$ holds. (Do you see why?)

Then,

$$\vec{c} = M^{-1}C' = \frac{1}{n} M_n(w^{-1}) = \frac{1}{4} \begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & -i & -1 & i \\ 1 & -1 & 1 & -1\\ 1 & i & -1 & -i \end{bmatrix} \begin{bmatrix} 16 \\ 0\\ 8 \\ 0 \end{bmatrix} = \begin{bmatrix} (16 + 8) /4 \\ (16 - 8) /4 \\ (16 + 8) /4 \\ (16 - 8) /4 \end{bmatrix} = \begin{bmatrix} 6 \\ 2\\ 6 \\ 2 \end{bmatrix}$$

Thus, we get the polynomial

$$C = A * B = 6 + 2x + 6x^2 + 2x^3$$ ¹: Inversion Formula pg 73, Algorithms by Dasgupta et. al. (C) 2006