I need to compute only a small number of low frequency Fourier components of a complex 2-dimensional array. I'll be computing the same Fourier components over and over again as the input array changes. Clearly, in the limit where I only want one Fourier component, it would be fastest to build a DFT matrix that gives the component I'm after, and multiply by that matrix repeatedly.In the other limit, if I wanted all Fourier components, it would be faster to use an FFT.At what point does it become faster to compute the FFT of the array and simply pull out the components that I'm after?If it makes a difference, in my particular situation the input array will be something like $256\times256$. I'm using MATLAB, so that means my FFT is done using FFTW, and a matrix multiplication for a matrix DFT is done via whatever matrix multiply algorithm MATLAB uses under the hood.
How many Fourier magnitudes do I have to calculate before an FFT becomes more efficient than a DFT?
matlab;fourier analysis
17.Lots and lots of work has gone into good fft implementations and it's unlikely you'll be able to reliably outperform a good fft library. For example, fftw automatically adapts itself to your machine, your cache, the size of your memory, the number of registers, and all the other factors that normally make it impossible to optimize a program for more than one machine ref this page.You are right that there are situations where it's faster to just compute a few dot products but it's going to be very system dependent.An experiment:EDU>> n = 256^2;EDU>> x = randn(n,1);EDU>> d = randn(1,n); %really, you should take a row from the output of the dftmtx command. But dftmtx(n) won't fit on my laptop...EDU>> tic;d*x;toc; %time to compute a single frequency from the dft matrixElapsed time is 0.000225 seconds.EDU>> tic;fft(x);toc; %time to compute the entire fftElapsed time is 0.003909 seconds.So when there's 4096 data points computing the whole fft takes only ~17x longer than computing a single dot product.