FFTW (the Fastest Fourier Transform in the West) is a famous library implementing an FFT algorithm. It was developed at MIT by Matteo Frigo and Steven G. Johnson and is distributed under a GPL license.
By popular demand, Madagascar's FFT-based programs (such as sffft1 and sffft3) include now an optional support for FFTW. The presence of the FFTW single-precision library is detected during compilation.
The following table shows some peformance measurements (CPU time in seconds for 1,000 complex-valued FFTs using sffft3):