Say you have two polynomials: $3 + x$ and $2x^2 + 2$.
I'm trying to understand how FFT helps us multiply these two polynomials. However, I can't find any worked out examples. Can someone show me how FFT algorithm would multiply these two polynomials. (Note: there is nothing special about these polynomials, but I wanted to keep it simple to make it easier to follow.)
I've looked at the algorithms in pseudocode, but all of them seem to be have problems (don't specify what the input should be, undefined variables). And surprisingly, I can't find where anyone has actually walked through (by hand) an example of multiplying polynomials using FFT.
Asked By : lars
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/16266
Answered By : Yuval Filmus
Suppose we use fourth roots of unity, which corresponds to substituting $1,i,-1,-i$ for $x$. We also use decimation-in-time rather than decimation-in-frequency in the FFT algorithm. (We also apply bit-reversal seamlessly.)
In order to compute the transform of the first polynomial, we start by writing the coefficients: $$ 3,1,0,0. $$ The Fourier transform of the even coefficients $3,0$ is $3,3$, and of the odd coefficients $1,0$ is $1,1$. (This transform is just $a,b \mapsto a+b,a-b$.) Therefore the transform of the first polynomial is $$ 4,3-i,2,3+i. $$ This is obtained using $X_{0,2} = E_0 \pm O_0$, $X_{1,3} = E_1 \mp i O_1$. ( From twiddle factor calculation ).
Let's do the same for the second polynomial. The coefficients are $$2,0,2,0.$$ The even coefficients $2,2$ transform to $4,0$, and the odd coefficients $0,0$ transform to $0,0$. Therefore the transform of the second polynomial is $$ 4,0,4,0. $$
We obtain the Fourier transform of the product polynomial by multiplying the two Fourier transforms pointwise: $$ 16, 0, 8, 0. $$ It remains to compute the inverse Fourier transform. The even coefficients $16,8$ inverse-transform to $12,4$, and the odd coefficients $0,0$ inverse-transform to $0,0$. (The inverse transform is $x,y \mapsto (x+y)/2,(x-y)/2$.) Therefore the transform of the product polynomial is $$6,2,6,2.$$ This is obtained using $X_{0,2} = (E_0 \pm O_0)/2$, $X_{1,3} = (E_1 \mp i O_1)/2$. We have obtained the desired answer $$ (3 + x)(2 + 2x^2) = 6+2x+6x^2+2x^3. $$
Post a Comment