Say i'm trying to evaluate the Polynomial:
x^2 + 1
Using the Fast Fourier transform method for evaluating coefficients. Now i can change this into matrix/vector form using the coeffcient 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 i1i
11 1i
1i 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)?

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} * i^{2} = i^{2} = 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^{2} + 1 isn't large. 16 terms is not large, and even 64 or 256 terms is probably better done by straightforward O(N^{2}) 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 N1.
Fast Fourier Transforms never use this matrix directly, they are heavily optimized to use a divideandconquer technique (CooleyTukey 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 i1i 11 11 1i1 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.
0 comments:
Post a Comment