Fast Fourier Transform

[gam3r]

I'm having trouble with the whole concept of this. I've read my slides, books and searched the internet but still have no clue how to use it to multiply two polynomials together.

Bit of a long shot i know, but if anyone knows how this all works could you explain to me the multiplication of these two poly's step by step using the FFT?

1+x+2x^2 and
2+3x

Any help appreciated, been trying to make sense of this whole thing for ages now..

 

[gam3r]

Well, in answer to dangerstat's q, both are current problems i'm having

 

[gam3r]

Nope no convolution.

dangerstat: thanks for that explanation, its a bit more clearer now, but how would i go about using that theory with the polynomial multiplication?

here is the "steps" from the book, i don't understand them!

1. Selection:
Pick some points x0; x1; : : : xn-1, where n 2d + 1
2. Evaluation:
Compute A(x0); A(x1); : : : A(xn-1), B(x0); B(x1); : : : B(xn-1)
3. Multiplication:
Compute C(xk) = A(xk)B(xk) for all k = 0; : : : n - 1
4. Interpolation: Recover C(x) = c0 + c1x + : : : + c2dx2d

 

[gam3r]

Theoretically yes, but the problem is i have no idea where to start

 

[gam3r]

Yup, im trying to do it while showing working if you know what i mean!

 

[gam3r]

Well after a few months i'm still struggling to understand this!

This is how far i've got..

I've got 2 Polynomials:
3x+2
2x^2 + x + 1

Using coefficient representation:

3x+2 = (2,3,0,0)
2x^2 + x + 1 = (1,1,2,0)

Now i'm stuck. Here is the solution. I don't understand the part where it converts these two things to :

FFT(1, 1, 2, 0) = (4, 11+i, 2,−1−i)
FFT(2, 3, 0, 0) = (5, 2 + 3i,−1, 2 − 3i)

Anyone explain this? I know it's a long shot!

Here is the actual solution:

 

[gam3r]

If its acceptable to calculate that way you could just left multiply your polynomial vectors by the 4x4 DFT matrix.

And how would you do that

 

[gam3r]

With the correct normalisation the matrix you want to use is I think

   1  1  1  1
   1  i -1 -i
   1 -1  1 -1
   1 -i -1  i

If you make a column vector from your polynomial coefficients and multiply it on the right of that matrix you should get your fourier coefficients.

To be clear

   1  1  1  1       1       4
   1  i -1 -i   \/  1  =   -1 + i
   1 -1  1 -1   /\  2      2
   1 -i -1  i       0      -1 - i

There seems to be a typo in your solution.

Thanks for your help buddy,
how did you determine the "correct normalisation matrix"?

 

[gam3r]

I see the vandermonde matrix with all the w's but i'm not sure as to how we got

1 1 1 1
1 i -1 -i
1-1 1 -1
1 -i -1 i

from the nxn vandermonde...

 

[gam3r]

Lol. I'm so confused!

I thought the formula was e^2pi/n ?

aaaaaaaaaaaahhhhhhhhhh