Digamos que tiene dos polinomios: y .
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.
Respuestas:
Supongamos que usamos la cuarta raíz de la unidad, que corresponde a la sustitución de1,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,b↦a+b,a−b .) Por lo tanto, la transformación del primer polinomio es
4,3+i,2,3−i.
Esto se obtiene usandoX0,2=E0±O0 ,X1,3=E1∓iO1 . (Del cálculo del factor twiddle).
Hagamos lo mismo para el segundo polinomio. Los coeficientes son2,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,(x−y)/2 ) Por lo tanto, la transformación del polinomio del producto es
6,2,6,2.
Esto se obtiene usandoX0 , 2= ( E0 0± O0 0) / 2 ,X1 , 3= ( E1∓ i O1) / 2 . Hemos obtenido la respuesta deseada
(3+x)(2+2x2)=6+2x+6x2+2x3.
fuente
Define the polynomials, where
deg(A) = q
anddeg(B) = p
. Thedeg(C) = q + p
.In this case,
deg(C) = 1 + 2 = 3
.Podemos encontrar fácilmente C en el tiempoO(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:
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,n≥deg(C) . Thus n=4 . Choosing a power of two provides us a way to recursively apply our divide-and-conquer algorithm.
LetA′,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
We defineM=Mn(ω) where ω is complex roots nth complex roots of unity. Notice jth row and kth column is ωjkn . See more about the DFT matrix here
n = 4
, in this example. Also notice that the entry in theGiven theω4=4th roots of unity, we have the ordered set equality:
This can be visualized as iterating thru roots of the unit circle in the counter-clockwise direction.
Also, notice theω6=ω6modn=ω2=−1 and −i=ω3=ω3+n
mod n
nature, i.e.To complete step 1 (evaluation) we findA′,B′ by performing
This step can be achieved using D&C algorithms (beyond the scope of this answer).
MultiplyA′∗B′ component-wise (step 2)
Finally, the last step is to represent C' into coefficients. Notice
NoticeM−1n=1nMn(ω−1) 1 and ωj=−ωn/2+j .
Also, it is true that, given thenth root of unity, the equality ω−j=ωn−j holds. (Do you see why?)
Then,c⃗ =M−1C′=1nMn(w−1)=14⎡⎣⎢⎢⎢11111−i−1i1−11−11i−1−i⎤⎦⎥⎥⎥⎡⎣⎢⎢⎢16080⎤⎦⎥⎥⎥=⎡⎣⎢⎢⎢⎢(16+8)/4(16−8)/4(16+8)/4(16−8)/4⎤⎦⎥⎥⎥⎥=⎡⎣⎢⎢⎢6262⎤⎦⎥⎥⎥
Thus, we get the polynomialC=A∗B=6+2x+6x2+2x3
1: Inversion Formula pg 73, Algorithms by Dasgupta et. al. (C) 2006
fuente