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.
- Developer: Matteo Frigo and Steven G. Johnson
- Contact: fftw@fftw.org
- Number of sites: several thousand
- Number of users: several thousand, plus a few commercial licensees
- In use: since 1997
- Language: Objective Caml
- Compilers: ocamlopt
- Line count: about 4000
- Availability:
Free for non-commercial use from
the FFTW home page.
- Related publications:
M. Frigo and S. G. Johnson, "The Fastest Fourier Transform
in the West," MIT Laboratory for Computer Science technical report
MIT-LCS-TR-728 (September 1997)
M. Frigo and S. G. Johnson, "FFTW: An Adaptive Software
Architecture for the FFT," Proc. ICASSP 1998.
M. Frigo, "A Fast Fourier Transform Compiler," Proceedings of the 1999 ACM
SIGPLAN Conference on Programming Language Design and Implementation (PLDI
'99), Atlanta, Georgia, May 1999.