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

Question

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)?

Answer 1

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).

Answer 2

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.