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.

algorithms fourier-transform divide-and-conquer

— lars
źródło

Wikipedia zachowuje ten ładny obraz do mnożenia liczb całkowitych za pomocą FFT, ale myślę, że nawet bardziej szczegółowy krok po kroku może być pomocny.

— Realz Slaw

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.

$3,1,0,0.$ Przekształcenie Fouriera parzystych współczynników

3, 0

$3,0$ wynosi

3, 3

$3,3$ , a nieparzystych współczynników

1, 0

$1,0$ wynosi

1, 1

$1,1$ . (Ta transformacja jest po prostu

a, b \mapsto a + b, a - b

$a,b \mapsto a+b,a-b$ .) Dlatego transformacja pierwszego wielomianu wynosi

4, 3) + ja, 2), 3) - ja .

$4,3+i,2,3-i.$ Uzyskuje się to, stosując

X_{0, 2} = E_{0} \pm O_{0}

$X_{0,2} = E_0 \pm O_0$ ,

X_{1, 3} = E_{1} \mp i O_{1}

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

$2,0,2,0.$ Parzyste współczynniki

2, 2

$2,2$ przekształcają się na

4, 0

$4,0$ , a nieparzyste współczynniki

0, 0

$0,0$ przekształcają się na

0, 0

$0,0$ . Dlatego transformacja drugiego wielomianu wynosi

4, 0, 4, 0.

$4,0,4,0.$

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

16, 0, 8, 0.

$16, 0, 8, 0.$ Pozostaje obliczyć odwrotną transformatę Fouriera. Współczynniki parzyste

16, 8

$16,8$ odwrotnej transformacji do

12, 4

$12,4$ , a nieparzyste współczynniki

0, 0

$0,0$ odwrotnej transformacji do

0, 0

$0,0$ . (Odwrotna transformata to

x, y \mapsto (x + y) / 2, (x - y) / 2

$x,y \mapsto (x+y)/2,(x-y)/2$ ) Zatem transformacja wielomianu produktu wynosi

6, 2, 6, 2)

$6,2,6,2.$ Jest to uzyskiwane przy użyciu

X_{0, 2} = (E_{0} \pm O_{0}) / 2

$X_{0,2} = (E_0 \pm O_0)/2$ ,

X_{1, 3} = (E_{1} \mp i O_{1}) / 2

$X_{1,3} = (E_1 \mp i O_1)/2$ . Otrzymaliśmy pożądaną odpowiedź

(3 + x) (2 + 2 x^{2}) = 6 + 2 x + 6 x^{2} + 2 x^{3} .

$(3 + x)(2 + 2x^2) = 6+2x+6x^2+2x^3.$

— Yuval Filmus
źródło

jak doszedłeś do 6,2 6, 2?

— lars

wzory:

, gdzie

(

) wynosi odwrotna transformacja parzystych (nieparzystych) współczynników, uzyskana ze wzoru

X_{0, 2} = (E_{0} \pm O_{2}) / 2

$X_{0,2} = (E_0 \pm O_2)/2$

X_{1, 3} = (E_{1} \mp i O_{1}) / 2

$X_{1,3} = (E_1 \mp i O_1)/2$

E_{0}, E_{1}

$E_0,E_1$

O_{1}, O_{2}

$O_1,O_2$

. Proszę spojrzeć ponownie na odpowiedź - wszystkie obliczenia są dostępne.

x, y \mapsto (x + y) / 2, (x - y) / 2

$x,y \mapsto (x+y)/2,(x-y)/2$

— Yuval Filmus

Dlaczego dwa razy używasz parzystych współczynników? 3,3 -> 3,3,3,3. -> 3 + 1, 3-i, 3 + -1,3 - i?

— Aage Torleif,

Jak te formuły dla

rozciągają się na wyższe stopnie? Czy znaki plus / minus po prostu przewracają się? Na przykład, co by to było dla

X_{0, 2}

$X_{0,2}$

X_{1, 3}

$X_{1,3}$

X_{0, 2, 4}

$X_{0,2,4}$

— Bobby Lee,

@BobbyLee Zachęcam do przeczytania literatury na temat FFT.

— Yuval Filmus

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

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

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.
Pomnóż składowe wielomianów w ich reprezentacji wartości. Zwraca reprezentację wartości C = A * B. To zajmuje $O(n)$ czas.
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{aligned} A = 3 + x + 0 x^{2} + 0 x^{3} \Rightarrow & \vec{a} = [3, 1, 0, 0] \\ B = 2 + 0 x + 2 x^{+} 0 x^{3} \Rightarrow & \vec{b} = [2, 0, 2, 0] \end{aligned}

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

$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{matrix} 1 & 1 & 1 & . . . & 1 \\ 1 & ω^{1} & ω^{2} & . . . & ω^{n - 1} \\ 1 & ω^{2} & ω^{4} & . . . & . . . \\ . . . & . . . & . . . & ω^{j k} & . . . \\ 1 & ω^{n - 1} & ω^{2 (n - 1)} & . . . & ω^{(n - 1) (n - 1)} \end{matrix}] = [\begin{matrix} 1 & 1 & 1 & 1 \\ 1 & ω & ω^{2} & ω^{3} \\ 1 & ω^{2} & ω^{4} & ω^{6} \\ 1 & ω^{3} & ω^{6} & ω^{9} \end{matrix}]

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

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

$\{\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{matrix} 1 & 1 & 1 & 1 \\ 1 & ω & ω^{2} & ω^{3} \\ 1 & ω^{2} & ω^{4} & ω^{6} \\ 1 & ω^{3} & ω^{6} & ω^{9} \end{matrix}] [\begin{matrix} 3 \\ 1 \\ 0 \\ 0 \end{matrix}] = [\begin{matrix} 3 + 1 \\ 3 + 1 ω \\ 3 + ω^{2} \\ 3 + ω^{3} \end{matrix}] = [\begin{matrix} 4 \\ 3 + i \\ 2 \\ 3 - i \end{matrix}] B^{'} = M * \vec{b} = [\begin{matrix} 1 & 1 & 1 & 1 \\ 1 & ω & ω^{2} & ω^{3} \\ 1 & ω^{2} & ω^{4} & ω^{6} \\ 1 & ω^{3} & ω^{6} & ω^{9} \end{matrix}] [\begin{matrix} 2 \\ 0 \\ 2 \\ 0 \end{matrix}] = [\begin{matrix} 2 + 2 \\ 2 + 2 ω^{2} \\ 2 + 2 ω^{4} \\ 2 + 2 ω^{6} \end{matrix}] = [\begin{matrix} 4 \\ 0 \\ 4 \\ 0 \end{matrix}]

$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{matrix} 4 \\ 3 + i \\ 2 \\ 3 - i \end{matrix}] [\begin{matrix} 4 \\ 0 \\ 4 \\ 0 \end{matrix}] = [\begin{matrix} 16 \\ 0 \\ 8 \\ 0 \end{matrix}] = C^{'}

$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^{'}

$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{matrix} 1 & 1 & 1 & 1 \\ 1 & ω^{- 1} & ω^{- 2} & ω^{- 3} \\ 1 & ω^{- 2} & ω^{- 4} & ω^{- 6} \\ 1 & ω^{- 3} & ω^{- 6} & ω^{- 9} \end{matrix}] = \frac{1}{4} [\begin{matrix} 1 & 1 & 1 & 1 \\ 1 & - i & - 1 & i \\ 1 & - 1 & 1 & - 1 \\ 1 & i & - 1 & - i \end{matrix}]

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

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

$\{\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{matrix} 1 & 1 & 1 & 1 \\ 1 & - i & - 1 & i \\ 1 & - 1 & 1 & - 1 \\ 1 & i & - 1 & - i \end{matrix}] [\begin{matrix} 16 \\ 0 \\ 8 \\ 0 \end{matrix}] = [\begin{matrix} (16 + 8) / 4 \\ (16 - 8) / 4 \\ (16 + 8) / 4 \\ (16 - 8) / 4 \end{matrix}] = [\begin{matrix} 6 \\ 2 \\ 6 \\ 2 \end{matrix}]

$\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 + 2 x + 6 x^{2} + 2 x^{3}

— j__gt
źródło