The Fastest Fourier Transform in the West
Abstract
This paper describes FFTW, a portable C package for computing the one- and multidimensional complex discrete Fourier transform "DFT". FFTW is typically faster than all other publicly available DFT software, including the well-known FFTPACK and the code from Numerical Recipes. More interestingly, FFTW is competitive with or better than proprietary, highly-tuned codes such as Sun's PerformanceLibrary and IBM'sESSL library. FFTW implements the Cooley-Tukey fast Fourier transform, and is freely available on the Web at http://theory.lcs.mit.edu/ fftw. Three main ideas are the keys to FFTW's performance. First, the computation of the transform is performed by an executor consisting of highly-optimized, composable blocks of C code called codelets. Second, at runtime, a planner finds an efficient way "called a `plan'" to compose the codelets. Through the planner, FFTWadapts itself to the architecture of the machine it is running on. Third, the codelets are automatically generated by a codelet generator written in the Caml Light dialect of ML. The codelet generator produces long, optimized, unreadable code, which is nevertheless easy to modify via simple changes to the generator.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 11, 1997
- Accession Number
- ADA479232
Entities
People
- Matteo Frigo
- Steven G. Johnson
Organizations
- Massachusetts Institute of Technology