FFTW

FFTW is a fast C library for computing the Fast Fourier Transform (FFT) in one or more dimensions, including real-complex and parallel transforms. It is typically faster than most other public-domain FFT software, and is even competitive with vendor-optimized libraries for specific hardware (see the benchmarks on our home page).

The performance-critical code in FFTW was automatically generated by a program written in Objective Caml. The generated code consists of specialized transforms for small sizes, dubbed "codelets," which are composed dynamically at runtime for optimal performance. Our generator enables us to incorporate a number of sophisticated FFT algorithms, apply many tedious optimizations, and generate thousands of lines of highly-optimized C code. (We found Caml to be a really appropriate language for this sort of thing with its facility in symbolic manipulations and pattern matching.) For more details regarding the codelet generator in FFTW, see the papers available from our home page.

Recently, FFTW's generator program has gained in sophistication. It can now derive new algorithms for real FFTs and discrete cosine/sine transforms simply by applying the appropriate symmetries to the complex algorithms and simplifying.

For further information, see the FFTW home page.