For the plain ol' FFT, I've found the "Fastest Fourier in the West": http://www.fftw.org/ http://www.fftw.org/ to be an excellent library, which implements a wh

For the plain ol' FFT, I've found the "Fastest Fourier in the West": http://www.fftw.org/ http://www.fftw.org/ to be an excellent library, which implements a whole bunch of different solvers, and picks the appropriate ones to use for your data. Hopefully this new algorithm can be added to their toolbox in the future.