Sunday, May 1, 2011

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:


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




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)0, (-i)1, (-i)2, (-i)3. Note in particular that

    (-i)*(-i) = (-1)2 * i2 = i2 = -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. x2 + 1 isn't large. 16 terms is not large, and even 64 or 256 terms is probably better done by straightforward O(N2) techniques.

    Discrete Fourier Transforms use the matrix Mij = ω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: You take the complex conjugate of the matrix and divide by N = the vector length.


Post a Comment