9 - The Fast Fourier Transform or FFT

Summary

It [the FFT] also dominates the search for offshore oil. Water layers produce “ringing” that masks the signals from oil or gas; those primary reflections could not be seen before 1960. Now virtually all exploration data is digital and more than 10⁹ systems of equations are solved every year – partly by the FFT and partly by Levinson's algorithm for constant-diagonal (Toeplitz) matrices. The key problem is deconvolution…

Strang [1986, p. 467].

Despite a fear of oil slicks on the beach in Encinitas, we want to sketch the theory of the fast Fourier transform or FFT. The simplest version of this transform allows one to compute the DFT on a finite cyclic group of order n = 2^k elements in n log w operations rather than n² operations. Other algorithms exist if n is not a power of 2 but we will not discuss them here. The FFT has revolutionized digital signal processing.

We are mostly following the discussion in G. Strang [1986]. The FFT is usually attributed to Cooley and Tukey [1965]. However, Heidemann et al. [1984] note that the Cooley-Tukey algorithm was essentially known to Gauss in 1805, which is two years before Fourier and 160 years before Cooley and Tukey.

Brigham [1974] says that R. L. Garwin asked Tukey to give him a rapid way to compute the Fourier transform during a meeting of the President's Scientific Advisory Committee.