Fast Fourier Transform (FFT) Algorithms

The term fast Fourier transform (FFT) refers to an efficient implementation of the discrete Fourier transform (DFT) for highly composite^A.1 transform lengths $N$ . When computing the DFT as a set of $N$ inner products of length $N$ each, the computational complexity is ${\cal O}(N^2)$ . When $N$ is an integer power of 2, a Cooley-Tukey FFT algorithm delivers complexity ${\cal O}(N\lg N)$ , where $\lg N$ denotes the log-base-2 of $N$ , and ${\cal O}(x)$ means ``on the order of $x$ ''. Such FFT algorithms were evidently first used by Gauss in 1805 [31] and rediscovered in the 1960s by Cooley and Tukey [17].

In this appendix, a brief introduction is given for various FFT algorithms. A tutorial review (1990) is given in [23]. Additionally, there are some excellent FFT ``home pages'':

• http://en.wikipedia.org/wiki/Category:FFT_algorithms
• http://faculty.prairiestate.edu/skifowit/fft/

Pointers to FFT software are given in §A.7.