As fast as matrix multiplication may be, for large N, it is never fast enough. Fortunately, Cooley and Tukey wrote a paper in 1965 describing how to speed up the process. (This is, by the way, the most-cited paper in all of computer science and mathematics!) The FFT, as it is called, runs in time O(N logN), as compared with O(N2) for matrix multiplication. This makes it feasible to do Fourier transforms on mega-pixel images in a reasonable time. The FFT is fastest when the number of elements is a power of 2 (e.g., 32,64,128,256,512,1024,...) In IDL, the forward transform is FFT(f,1) and the inverse transform is FFT(f,-1). The FFT performs the following function, except faster:
|
function fft_sim,f ; simulates the function FFT(f,1) |
 |
i=complex(0,1) |
|
n=n_elements(f) |
|
c=complexarr(n) |
|
z=findgen(n)/float(n) |
|
for k=0,n-1 do c(k)=total(f*exp(2*!pi*i*k*z)) |
|
return,f |
|
end |
Exercise:
Run the above program using at least 2048 elements, and perform the same calculation with FFT. Compare the speed as the number of elements is doubled.