FFTW

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