Mostrar cómo hacer FFT a mano

27

Digamos que tiene dos polinomios: 3+x y .2x2+2

Estoy tratando de entender cómo FFT nos ayuda a multiplicar estos dos polinomios. Sin embargo, no puedo encontrar ningún ejemplo resuelto. ¿Alguien puede mostrarme cómo el algoritmo FFT multiplicaría estos dos polinomios? (Nota: no hay nada especial en estos polinomios, pero quería que fuera simple para que sea más fácil de seguir).

He mirado los algoritmos en pseudocódigo, pero todos parecen tener problemas (no especifique cuál debería ser la entrada, variables indefinidas). Y sorprendentemente, no puedo encontrar por dónde alguien haya caminado (a mano) un ejemplo de multiplicación de polinomios usando FFT.

lars
fuente
2
Wikipedia mantiene esta buena imagen para la multiplicación de enteros a través de FFT, pero creo que un paso a paso aún más explícito podría ser útil.
Realz Slaw

Respuestas:

27

Supongamos que usamos la cuarta raíz de la unidad, que corresponde a la sustitución de 1,i,1,i por x . También usamos decimación en tiempo en lugar de decimación en frecuencia en el algoritmo FFT. (También aplicamos una operación de inversión de bits sin problemas).

Para calcular la transformada del primer polinomio, comenzamos escribiendo los coeficientes:

3,1,0,0.
La transformada de Fourier de los coeficientes pares 3,0 es 3,3 , y de los coeficientes impares 1,0 es 1,1 . (Esta transformación es solo a,ba+b,ab .) Por lo tanto, la transformación del primer polinomio es
4,3+i,2,3i.
Esto se obtiene usandoX0,2=E0±O0 ,X1,3=E1iO1 . (Del cálculo del factor twiddle).

Hagamos lo mismo para el segundo polinomio. Los coeficientes son

2,0,2,0.
Los coeficientes pares 2,2 transforman en 4,0 , y los coeficientes impares 0,0 transforman en 0,0 . Por lo tanto, la transformación del segundo polinomio es
4,0,4,0.

Obtenemos la transformada de Fourier del polinomio del producto multiplicando las dos transformadas de Fourier puntiagudas:

16,0,8,0.
Queda por calcular la transformada inversa de Fourier. Los coeficientes pares 16,8 transforman inversamente a 12,4 , y los coeficientes impares 0,0 transforman inversa a 0,0 . (La transformación inversa es x,y(x+y)/2,(xy)/2 ) Por lo tanto, la transformación del polinomio del producto es
6,2,6,2.
Esto se obtiene usandoX0 0,2=(mi0 0±O0 0)/ /2 ,X1,3=(mi1yoO1)/ /2 . Hemos obtenido la respuesta deseada
(3+x)(2+2x2)=6+2x+6x2+2x3.

Yuval Filmus
fuente
¿Cómo llegaste a 6,2 6, 2?
lars
Di las fórmulas: , X 1 , 3 = ( E 1i O 1 ) / 2 , donde E 0 , E 1 ( O 1 , O 2 ) es la transformación inversa de los coeficientes pares (impares), obtenidos a través de la fórmula x , y ( x + y )X0,2=(E0±O2)/2X1,3=(E1iO1)/2E0,E1O1,O2 . Mire la respuesta nuevamente: todos los cálculos están ahí. x,y(x+y)/2,(xy)/2
Yuval Filmus
¿Por qué usas los coeficientes pares dos veces? 3,3 -> 3,3,3,3. -> 3 + 1, 3-i, 3 + -1,3 - i?
Aage Torleif
How do these formulas for X0,2 and X1,3 extend to higher degrees? Do the plus/minus signs just keep flipping? For example what would it be for X0,2,4 ?
Bobby Lee
@BobbyLee I encourage you to read some literature on FFT.
Yuval Filmus
7

Define the polynomials, where deg(A) = q and deg(B) = p. The deg(C) = q + p.

In this case, deg(C) = 1 + 2 = 3.

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

Podemos encontrar fácilmente C en el tiempo O(n2) multiplicando por fuerza bruta los coeficientes. Al aplicar FFT (y FFT inversa), podríamos lograr esto en el tiempo O(nlog(n)) . Explícitamente:

  1. Convierta el coeficiente de representación de A y B en su representación de valor. Este proceso se llama evaluación . Realizar Divide-and-Conquer (D&C) para esto llevaría tiempo O(nlog(n)) .
  2. Multiply component-wise the polynomials in their value representation. This returns the value representation of C = A*B. This take O(n) time.
  3. Invert C using inverse FFT to get C in its coefficient representation. This process is called interpolation and it also takes O(nlog(n)) time.

Continuing along, we represent each polynomial as a vector whose value are its coefficients. We pad the vector with 0's up to the smallest power of two, n=2k,ndeg(C). Thus n=4. Choosing a power of two provides us a way to recursively apply our divide-and-conquer algorithm.

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

Let A,B be the value representation of A and B, respectively. Notice that FFT (Fast Fourier Transform) is a linear transformation (linear map) and can be represented as a matrix, M. Thus

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
fuente