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):

data length KISS FFT FFTW
4,096 0.11 0.08
8,192 0.27 0.18
16,384 0.50 0.32
32,768 1.21 0.80
65,536 2.61 1.78