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$. Such FFT algorithms were evidently first used by Gauss in 1805 [29] and rediscovered in the 1960s by Cooley and Tukey [14].

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