Chapter notes

VanLoan's book [303] is an outstanding treatment of the Fast Fourier Transform. Press, Flannery, Teukolsky, and Vetterling [248, 249] have a good description of the Fast Fourier Transform and its applications. For an excellent introduction to signal processing, a popular FFT application area, see the texts by Oppenheim and Schafer [232] and Oppenheim and Willsky [233]. The Oppenheim and Schafer book also shows how to handle cases in which n is not an integer power of 2.

Fourier analysis is not limited to 1-dimensional data. It is widely used in image processing to analyze data in 2 or more dimensions. The books by Gonzalez and Woods [127] and Pratt [246] discuss multdimensional Fourier Transform and their use in image processing, and books by Tolimieri, An, and Lu [300] and Van Loan [303] discuss the mathematics of multidimensional Fast Fourier Transforms.

Cooley and Tukey [68] are widely credited with devising the FFT in the 1960's. The FFT had in fact been discovered many times previously, but its importance was not fully realized before the advent of modern digitial computers. Although Press, Flannery, Teukolsky, and Vetterling attribute the origins of the method of Runge and König in 1924, an article by Heideman, Johnson, and Burrus [141] traces the history of the FFT as far back as C. F. Gauss in 1805.