Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

This wikibook states that the output of MATLAB's FFT corresponds with the wavenumbers ordered as:

$$k=\left\{0,1,...,\frac{n}{2},-\frac{n}{2}+1,-\frac{n}{2}+2,...,-1\right\}$$

However, in the example codes on the same page, the wavenumbers are coded as

k = [0:n/2-1 0 -n/2+1:-1];

which is the same as the first, but with the $n/2$-wavenumber (the "maximum wavemnumber") replaced with $0$. It seems strange that they would include $0$ twice.

It seems the correct order is necessary for taking derivatives via Fourier transforms, as described in the wikibook. Which of these is correct, and does MATLAB document this anywhere?

share|improve this question
2  
look into the function fftshift. It will take the output of fft, and reorder it from [-n/2+1 : n/2-1], which should help with your confusion. –  Godric Seer Feb 18 '13 at 18:05
add comment

1 Answer

I want to expand on my comment and rework the example you reference in a way that should be more understandable than the original and to explain why fft returns the coefficients the way it does.

For reference, the fft portion of the example is :

Nx = size(x,2);
k = 2*pi/(b-a)*[0:Nx/2-1 0 -Nx/2+1:-1];
dFdx = ifft(1i*k.*fft(f));
d2Fdx2 = ifft(-k.^2.*fft(f));

I added another section of code directly below it:

Nx = size(x,2);
k = 2*pi/(b-a)*(-Nx/2:Nx/2-1);
dFdxp = ifft(ifftshift(1i*k.*fftshift(fft(f))));
d2Fdx2p = ifft(ifftshift(-k.^2.*fftshift(fft(f))));

and wrapped both pieces of code in a tic; toc for rought timings. In a more readable format, the second method uses:

ckf = fftshift(fft(f));
ckdf = 1i*k.*ckf;
df = ifft(ifftshift(ckdf));

The first difference is that the second example has a much more intuitive k. This is the main advantage of the second example, since k is now in the form that we think about them. In the second and third lines I had to add fftshift around the call to fft, then a call to ifftshift directly inside the call to ifft. These additional function calls reorder the coefficients from what is required for the computer to work with them to the way humans usually think about them.

The issue with the second example, is that while k is more intuitive for us, this leaves the internal matrices for solving and inverting fft in forms that aren't as advantageous. So either we have to switch the order with calls to fftswitch and ifftswitch or it has to be hard coded into the fft functions. This is less prone to error from users (assuming they are unfamiliar with the workings of fft, as many people are), but you pay a price in run time.

As I stated before, I added timing calls around the two blocks for comparison and ran for multiple N. The timing results were:

N =     1000,  Ex1 = 0.000222 s,   Ex2 = 0.007072 s
N =    10000,  Ex1 = 0.001576 s,   Ex2 = 0.003506 s
N =   100000,  Ex1 = 0.023857 s,   Ex2 = 0.034051 s
N =  1000000,  Ex1 = 0.213816 s,   Ex2 = 0.406250 s
N = 10000000,  Ex1 = 4.555143 s,   Ex2 = 7.102348 s

As you can see, the act of switching the values back and forth slows the process considerably, especially at low N (where it 30x slower). This is just an example, and your computer may show slightly different trends depending on things such as memory speed, processor cores/speed, etc. but it is illustrative of the point. The reason fft has confusing output is because it is saving you a nontrivial fraction of your computing time.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.