Mostre como fazer a FFT manualmente

Digamos que você tenha dois polinômios: $3 + x$ e .$2x^2 + 2$

Estou tentando entender como a FFT nos ajuda a multiplicar esses dois polinômios. No entanto, não consigo encontrar nenhum exemplo elaborado. Alguém pode me mostrar como o algoritmo FFT multiplicaria esses dois polinômios. (Observação: não há nada de especial nesses polinômios, mas eu queria simplificá-lo para facilitar o acompanhamento.)

Analisei os algoritmos no pseudocódigo, mas todos eles parecem ter problemas (não especifique qual deve ser a entrada, variáveis ​​indefinidas). E, surpreendentemente, não consigo encontrar por onde alguém realmente percorreu (manualmente) um exemplo de multiplicação de polinômios usando a FFT.

Suponha que usemos a quarta raiz da unidade, que corresponde à substituição de por . Também usamos decimação no tempo, em vez de decimação na frequência, no algoritmo FFT. (Também aplicamos uma operação de reversão de bits sem problemas.)$1,i,-1,-i$$x$

Para calcular a transformação do primeiro polinômio, começamos escrevendo os coeficientes: A transformada de Fourier dos coeficientes pares é e dos coeficientes ímpares é . (Essa transformação é apenas .) Portanto, a transformação do primeiro polinômio é Isso é obtido usando , . (Do cálculo do fator twiddle).

$$3,1,0,0.$$ $3,0$$3,3$$1,0$$1,1$$a,b \mapsto a+b,a-b$ $$4,3+i,2,3-i.$$ $X_{0,2} = E_0 \pm O_0$$X_{1,3} = E_1 \mp i O_1$

Vamos fazer o mesmo para o segundo polinômio. Os coeficientes são Os coeficientes pares transformam-se em e os coeficientes ímpares transformam-se em . Portanto, a transformação do segundo polinômio é

$$2,0,2,0.$$ $2,2$$4,0$$0,0$$0,0$ $$4,0,4,0.$$

Obtemos a transformação de Fourier do polinômio do produto multiplicando as duas transformadas de Fourier no sentido do ponto: Resta calcular a transformação de Fourier inversa. Os coeficientes pares transformam inversamente a e os coeficientes ímpares transformam inversamente a . (A transformação inversa é ) Portanto, a transformação do polinômio do produto é Isso é obtido usando , . Obtivemos a resposta desejada

$$16, 0, 8, 0.$$ $16,8$$12,4$$0,0$$0,0$$x,y \mapsto (x+y)/2,(x-y)/2$ $$6,2,6,2.$$ $X_{0,2} = (E_0 \pm O_0)/2$$X_{1,3} = (E_1 \mp i O_1)/2$ $$(3 + x)(2 + 2x^2) = 6+2x+6x^2+2x^3.$$

Defina os polinômios, onde deg(A) = qe deg(B) = p. A deg(C) = q + p.

Nesse caso deg(C) = 1 + 2 = 3,.

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

Podemos facilmente encontrar C no tempo $O(n^2)$ pela multiplicação da força bruta dos coeficientes. Aplicando a FFT (e a FFT inversa), conseguimos isso em $O(n\log(n))$ . Explicitamente:

1. Converta a representação do coeficiente de A e B na sua representação de valor. Esse processo é chamado de avaliação . Executar a divisão e conquista (D&C) para isso levaria tempo $O(n\log(n))$ .
2. Multiplique os polinômios em componentes em sua representação de valor. Isso retorna a representação do valor de C = A * B. Isso leva tempo $O(n)$ .
3. Inverta C usando FFT inverso para obter C em sua representação de coeficiente. Esse processo é chamado de interpolação e também leva tempo $O(n\log(n))$ .

Continuando, representamos cada polinômio como um vetor cujo valor são seus coeficientes. O vetor é preenchido com 0 até a menor potência de dois, $n = 2^k, n \geq deg(C)$ . Assim $n = 4$ . Escolher uma potência de dois nos fornece uma maneira de aplicar recursivamente nosso algoritmo de dividir e conquistar.

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

Seja $A', B'$ a representação do valor de A e B, respectivamente. Note-se que FFT (Fast Fourier Transform ) é uma transformação linear ( mapa linear ) e pode ser representado como uma matriz, $M$ . portanto

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

Nós definimos $M = M_n(\omega)$ onde $\omega$ é raízes complexos $n^{th}$ raízes complexos de unidade. Observe n = 4neste exemplo. Observe também que a entrada na coluna $j^{th}$ e $k^{th}$ é $\omega_n^{jk}$ . Veja mais sobre a matriz DFT aqui

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

Dadas as $\omega_4 = 4^{th}$ raízes da unidade, temos o conjunto de igualdade ordenada:

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

Isso pode ser visualizado como iterando pelas raízes do círculo da unidade no sentido anti-horário .

Observe também a mod nnatureza, ou seja, $\omega^6 = \omega^{6 \mod n} = \omega^{2} = -1$e$-i = \omega^{3} = \omega^{3+n}$

Para concluir a etapa 1 ( avaliação ), encontramos $A', B'$ executando

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

Esta etapa pode ser alcançada usando algoritmos D&C (além do escopo desta resposta).

$A' * B'$

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