The Fastest Fourier Transform in the West
Matteo Frigo, Steven G. Johnson · 1997
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 Performance Library and IBM's ESSL 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, FFTW adapts 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.