[shabble]

For the plain ol' FFT, I've found the "Fastest Fourier in the West": 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.

[saulrh]

In the paper, they state that they compared their implementation to FFTW and beat it handily.