History of the FFT

(Note: This is a somewhat technical history, an excerpt from a scholarly article written by one of our authors.)

The first appearance of the FFT, like so much of mathematics, can be traced back to Gauss (see M. T. Heideman, D. H. Johnson, and C. S. Burrus, "Gauss and the history of the fast Fourier transform," Archive for History of Exact Sciences 34 (1985), no. 3, 265-277). Gauss’s interests were in certain astronomical calculations (a recurrent area of application of the FFT) having to do with the interpolation of asteroidal orbits from a finite set of equally spaced observations. Surely the prospect of a huge laborious hand calculation was good motivation for the development of a fast algorithm. Fewer calculations also imply less opportunity for error, and hence are also more numerically stable! Gauss observes that a Fourier series of bandwidth N = N1 N2 can be broken up into a computation of the N2 subsampled DFTs of length N1 which are combined as N1 DFTs of length N2. Gauss’s algorithm was never published outside of his collected works.

A less general but still important version of the FFT, used for the efficient computation of the Hadamard and Walsh transforms, was first published in 1932 by the statistician Yates (F. Yates, "The design and analysis of factorial experiments," Imperial Bureau of Soil Science Technology Committee 35 (1937)). Yates’s "interaction algorithm" is a fast technique for computing the analysis of variance for a 2n-factorial design, and is described in almost any text on statistical design and analysis of experiments.

Another important predecessor is the work of Danielson and Lanczos (G. C. Danielson and C. Lanczos, "Some improvements in practical Fourier analysis and their application to X-ray scattering from liquids," Journal of the Franklin Institute 233 (1942), no. 4 and 5, 365-380 and 432-452), performed in the service of X-ray crystallography, another frequent user of FFT technology. Their "doubling trick" showed how to reduce a DFT in 2N points to two DFTs on N points using on N extra operations. Today it brings a smile to our faces as we note their problem sizes and timings: "Adopting these improvements the approximate times for Fourier analysis are 10 minutes for 8 coefficients, 25 minutes for 16 coefficients, 60 minutes for 32 coefficients, and 140 minutes for 64 coefficients." This indicates a running time of about .37N logN minutes for an N point DFT!

Despite these early discoveries of an FFT, it wasn’t until Cooley and Tukey’s article (J. W. Cooley and J. W. Tukey, "An algorithm for machine calculation of complex Fourier series," Mathematical Computation 19 (1965), 297-301) that the algorithm gained any notice. The story of their collaboration is an interesting one. Tukey arrived at the basic reduction while in a meeting of President Kennedy’s Science Advisory Committee where among the topics of discussion were techniques for off-shore detection of nuclear tests in the Soviet Union. Ratification of a proposed United States/Soviet Union nuclear test ban depended upon the development of a method for detecting the tests without actually visiting the Soviet nuclear facilities. One idea was to analyze seismological time series obtained from off-shore seismometers, the length and number of which would require fast algorithms for computing the DFT. Other possible applications to national security included the long-range acoustic detection of nuclear submarines.

Richard Garwin of IBM was another of the participants at this meeting, and when Tukey showed him this idea he immediately saw a wide range of potential applicability and quickly set to getting this algorithm implemented. He was directed to Cooley and, needing to hide the national security issues, instead told Cooley that he wanted the code for another problem of interest: the determination of the periodicities of the spin orientations in a 3-D crystal of He3. Cooley had other projects going on, and only after quite a lot of prodding did he sit down to program the "Cooley-Tukey" FFT. In short order, Cooley was published almost instantaneously (in 6 months!). This publication, as well as Garwin’s fervent proselytizing, did a lot to help publicize the existence of this (apparently) new fast algorithm.

The timing of the announcement was such that usage spread quickly. The roughly simultaneous development of analog to digital converters capable of producing digitized samples of a time-varying voltage at rates of 300,000 samples per second had already initiated something of a digital revolution and was also providing scientists with heretofore unimagined quantities of digital data to analyze and manipulate (just as is the case today!). Even the "standard" applications of Fourier analysis as an analysis tool for waveforms or solving PDEs (partial differential equations) meant that a priori there would be a tremendous interest in the algorithm. But even more, the ability to do this analysis quickly allowed scientists from new areas to try the DFT without having to invest too much time and energy in the exercise. I can do no better than to quote the introduction to the FFT from Numerical Recipes (a standard work on computer algorithms): "If you speed up any nontrivial algorithm by a factor of a million or so the world will beat a path towards finding useful applications for it." (See W. H. Press, B.P. Falnnery, S. A. Teukolsky, and W. T. Vettering, Numerical recipes in C: The art of scientific computing, Cambridge University Press, New York, 1988.)