Fast Fourier Transform using a Vandermonde Matrix - Evaluation of Co-efficients?

Say i'm trying to evaluate the Polynomial:

x^2 + 1

Using the Fast Fourier transform method for evaluating co-efficients. Now i can change this into matrix/vector form using the co-effcient as inputs for the fast fourier transform:

so:

x^2 + 1 = <1, 0, 1, 0>

This is done by using the coefficient value e.g 1 = 1, 0x^1 = 0, X^2 = 1 and so on

Now we get to the bit where i'm totally confused. I'm meant to use the vandermonde matrix :Vandermonde matrix ~ Wiki to evaluate these values into FFT Form using the matrix:

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

The output of

fft(1,0,1,0)

is

(2,0,2,0)

Now thats the step i don't quite understand, how did we use that matrix to get (2,0,2,0)?

From stackoverflow

• First, your Vandermonde matrix is incorrect. The (4,3) entry should be -1, not 1, since the fourth row should be (-i)⁰, (-i)¹, (-i)², (-i)³. Note in particular that

  (-i)*(-i) = (-1)² * i² = i² = -1.

  With this correction, the result follows from multiplying the Vandermonde matrix by the column vector (1,0,1,0).

  KP65 : ahh yes i was being careless! i can't believe i spent ages looking at it like this but now i finally get it. Now onto the next part :)

• Maybe you could explain what your overall goal is here. I have never heard of FFTs being used to evaluate polynomials. They are used to multiply polynomials, or to convolve signals (an equivalent task), but I wouldn't bother unless the polynomials/signals have a large number of terms. x² + 1 isn't large. 16 terms is not large, and even 64 or 256 terms is probably better done by straightforward O(N²) techniques.

  Discrete Fourier Transforms use the matrix M_ij = ω^ij where ω is the Nth complex root of 1 and column/row numbering goes from 0 to N-1.

  Fast Fourier Transforms never use this matrix directly, they are heavily optimized to use a divide-and-conquer technique (Cooley-Tukey algorithm) to calculate the end result through stages of 2x2 DFTs in series and parallel.

  If you write your vector as [0,1,0,1] instead of [1,0,1,0], I think you will see that if you multiply that by the matrix you gave, you'll get [0,2,0,2]. (Although you have an error, it's

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

  ) There must be some convention in the program you are using which reverses the order of the vector's coefficients.

  KP65 : thank you, i understand now. i was also wondering, if i want to turn [0,2,0,2] back to [0,1,0,1]? i know your meant to use the inverse of something.. but i'm not quite sure!

  Jason S : Look at the Wikipedia page on DFT: http://en.wikipedia.org/wiki/Discrete_Fourier_transform#Expressing_the_inverse_DFT_in_terms_of_the_DFT You take the complex conjugate of the matrix and divide by N = the vector length.