This manual documents FFTW Version 1.2.
FFTW is a collection of fast C routines for computing the Discrete Fourier Transform in one or more dimensions. FFTW is unique in two respects. First, it is not just optimized for arrays whose sizes are powers of 2, 3, or other small numbers. Instead, FFTW comes with a code generator that produces C programs for any particular array size you may care about. Second, it doesn't use a fixed strategy for performing the transform. There are usually many ways to decompose a big problem into small problems, and the optimal way often depends on many unpredictable factors. Unlike other programs, FFTW can find the optimal decomposition at runtime for the machine it is running on.
FFTW is usually faster (and sometimes much faster) than all other public-domain Fourier Transform programs found on The Net. For transforms whose size is a power of two, it compares favorably with the FFT codes in Sun's Performance Library and IBM's ESSL library. Moreover, FFTW's performance is portable, because FFTW automatically adapts itself to your machine, your cache, the size of your memory, the number of registers, and all the other factors that normally make it impossible to optimize a program for more than one machine. Even if you want to run the same program on two binary-compatible machines that have completely different performance characteristics, FFTW will run optimally on both, without requiring recompilation of the program.
Hence the name, "FFTW," which is an acronym for "Fastest Fourier Transform in the West." This claim is not completely true. It is very likely that FFTW is the fastest portable-C implementation of Cooley-Tukey derived algorithms, both in the West and the East. However, we are well aware that progress has been made since the original Cooley-Tukey paper in 1965. In particular, we know that Prime Factor Algorithms perform fewer floating-point operations; in fact, there exist public-domain PFA codes that are sometimes faster than FFTW. (One such code is the CWP FFT program, available from the Colorado School of Mines.) The generalized PFA (by C. Temperton) appears especially attractive; we plan to implement one of Temperton's algorithms in the near future.
An extensive comparison of FFTW's performance with that of other Fourier
transform codes has been made. The results are available on the Web at:
http://theory.lcs.mit.edu/~fftw/benchmark/benchmark.html