Pokaż, jak wykonać FFT ręcznie

Załóżmy, że masz dwa wielomiany: $3 + x$ i .$2x^2 + 2$

Próbuję zrozumieć, w jaki sposób FFT pomaga nam pomnożyć te dwa wielomiany. Nie mogę jednak znaleźć żadnych wypracowanych przykładów. Czy ktoś może mi pokazać, jak algorytm FFT pomnożyłby te dwa wielomiany. (Uwaga: nie ma nic specjalnego w tych wielomianach, ale chciałem, aby było to proste, aby ułatwić śledzenie.)

Patrzyłem na algorytmy w pseudokodzie, ale wszystkie wydają się mieć problemy (nie określaj, jakie powinny być dane wejściowe, niezdefiniowane zmienne). I, co zaskakujące, nie mogę znaleźć, gdzie ktoś faktycznie przeszedł (ręcznie), przykładu pomnożenia wielomianów za pomocą FFT.

Załóżmy, że używamy czwartego pierwiastka jedności, co odpowiada podstawieniu $1,i,-1,-i$ na $x$ . W algorytmie FFT używamy również decymacji w czasie, a nie decymacji w częstotliwości. (Bezproblemowo stosujemy również operację odwracania bitów.)

Aby obliczyć transformację pierwszego wielomianu, zaczynamy od wpisania współczynników:

$$3,1,0,0.$$ Przekształcenie Fouriera parzystych współczynników $3,0$ wynosi $3,3$ , a nieparzystych współczynników $1,0$ wynosi $1,1$ . (Ta transformacja jest po prostu $a,b \mapsto a+b,a-b$ .) Dlatego transformacja pierwszego wielomianu wynosi $$4,3+i,2,3-i.$$ Uzyskuje się to, stosując$X_{0,2} = E_0 \pm O_0$ ,$X_{1,3} = E_1 \mp i O_1$ . (Z obliczenia współczynnika twiddle).

Zróbmy to samo dla drugiego wielomianu. Współczynniki wynoszą

$$2,0,2,0.$$ Parzyste współczynniki $2,2$ przekształcają się na $4,0$ , a nieparzyste współczynniki $0,0$ przekształcają się na $0,0$ . Dlatego transformacja drugiego wielomianu wynosi $$4,0,4,0.$$

Otrzymujemy transformatę Fouriera wielomianu iloczynu przez pomnożenie dwóch transformat Fouriera punktowo:

$$16, 0, 8, 0.$$ Pozostaje obliczyć odwrotną transformatę Fouriera. Współczynniki parzyste $16,8$ odwrotnej transformacji do $12,4$ , a nieparzyste współczynniki $0,0$ odwrotnej transformacji do $0,0$ . (Odwrotna transformata to $x,y \mapsto (x+y)/2,(x-y)/2$ ) Zatem transformacja wielomianu produktu wynosi $$6,2,6,2.$$ Jest to uzyskiwane przy użyciu$X_{0,2} = (E_0 \pm O_0)/2$ ,$X_{1,3} = (E_1 \mp i O_1)/2$ . Otrzymaliśmy pożądaną odpowiedź $$(3 + x)(2 + 2x^2) = 6+2x+6x^2+2x^3.$$

Zdefiniuj wielomiany, gdzie deg(A) = qi deg(B) = p. The deg(C) = q + p.

W tym wypadku deg(C) = 1 + 2 = 3.

$$A = 3 + x \\ B = 2x^2 + 2 \\ C = A*B = ?$$

Możemy łatwo znaleźć C w czasie $O(n^2)$ poprzez pomnożenie współczynników przez brutalną siłę. Stosując FFT (i odwrotne FFT), moglibyśmy to osiągnąć w czasie $O(n\log(n))$ . Wyraźnie:

1. Konwertuj reprezentację współczynników A i B na jej reprezentację wartości. Ten proces nazywa się oceną . Wykonanie w tym celu podziału i zdobycia zajęłoby $O(n\log(n))$ czasu.
2. Pomnóż składowe wielomianów w ich reprezentacji wartości. Zwraca reprezentację wartości C = A * B. To zajmuje $O(n)$ czas.
3. Odwróć C za pomocą odwrotnego FFT, aby uzyskać C w jego reprezentacji współczynnika. Ten proces nazywa się interpolacją i zajmuje również czas $O(n\log(n))$ .

Kontynuując, reprezentujemy każdy wielomian jako wektor, którego wartością są jego współczynniki. Wypełniamy wektor zerami do najmniejszej potęgi dwóch, $n = 2^k, n \geq deg(C)$ . Zatem $n = 4$ . Wybór potęgi dwóch daje nam sposób na rekurencyjne zastosowanie naszego algorytmu dziel i zwyciężaj.

$$\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}$$

Niech $A', B'$ będzie reprezentacją wartości odpowiednio A i B. Należy zauważyć, że FFT (fast Fourier Transform ) jest transformacja liniowa ( liniową mapą ) i może być przedstawiony jako matrycy, $M$ . A zatem

$$A' = M \overrightarrow{a} \\ B' = M \overrightarrow{b}$$

Definiujemy $M = M_n(\omega)$ gdzie $\omega$ jest złożonymi pierwiastkami $n^{th}$ złożonymi pierwiastkami jedności. Zauważ n = 4, w tym przykładzie. Zauważ również, że wpis w wierszu $j^{th}$ i kolumnie $k^{th}$ to $\omega_n^{jk}$ . Zobacz więcej o matrycy DFT tutaj

$$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}$$

Biorąc pod uwagę $\omega_4 = 4^{th}$ pierwiastków jedności, mamy uporządkowany zbiór równości:

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

Można to wizualizować jako iterację przez pierwiastki koła jednostkowego w kierunku przeciwnym do ruchu wskazówek zegara .

Zwróć też uwagę na mod nnaturę, tj. $\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