I am just learning FFTs and I am trying to debug a problem in MATLAB.
I think I don't understand how is MATLAB's FFT function handling the polynomial powers, or I am doing something wrong manually. My problem is that it seems that positions 1 .. n-1 are reversed.
OK, here is a very simple example: p(x) = x and I would like to compute the 4th order FFT
On paper it would be:
w0 = 1; w1 = i; w2 = -1; w3 = -i; p(w0) = 1; p(w1) = i; p(w2) = -1; p(w3) = -i;
and for me it would mean the following in vector form:
p = [0,1,0,0] fft(p) = [1,i,-1,-i]
But what happens is this:
fft(p) ans = 1.0000 0 - 1.0000i -1.0000 0 + 1.0000i
It means that somehow MATLAB is looking at the roots of unity in a 0,3,2,1 order. Why is this happening or is it me who is doing something wrong?
Update
I'm even more confused now that I tried it in Maple and Wolfram Alpha.
In Maple it returns:
v:=Vector[row]([ 0 , 1 , 0 , 0 ], datatype=complex[8]); FourierTransform(v); Vector[row](4, {(1) = .500000000000000+0.*I, (2) = 0.-.5000000000*I, (3) = -.500000000000000+0.*I, (4) = 0.+.500000000000000*I})
In Wolfram Alpha it is:
fft([0,1,0,0]) returns: {0.5, 0.5 i, -0.5, -0.5 i}
So to sum up, here is how it looks totally different by using 4 different methods:
polynomial: x^2 or [0,1,0,0] FFT on paper: [1, i, -1, -i] in MATLAB: [1, -i, -1, i] in Maple: [0.5, -0.5i, -0.5, 0.5i] in Wolfram Alpha: [0.5, 0.5i, -0.5, -0.5i]