Fast Fourier Transform - Multiplying Polynomials?

Question

i just don't understand how to perform a FFT on two polynomials such as X^2+1 and X+1...can anyone step by step go through the process with me?

Thanks very much

Answer 1

Just use your polynomial coefficients as input for fft:

octave:16> poly1=[1 0 1 0]
poly1 =

   1   0   1   0

Note: this means x^2+1

octave:17> poly2=[1 1 0 0]
poly2 =

   1   1   0   0

octave:18> ifft( fft(poly1).*fft(poly2))
ans =

   1   1   1   1

This is the result. Interpret as x^3+x^2+x+1, which is the product of the two polynomials.

Answer 2

But really what is going on here is convolution.

ifft( fft(poly1).*fft(poly2))

is the equivalent of convolution (properly padded). And convolution can be interpreted as the multiplication of two polynomials. Go look up the definition of convolution (it's very simple) and work it out by hand on paper. I expect that it will shed a lot of light on this for you...

Paul
CenterSpace Software