The calculation of the Fourier coefficients using our equations involvesAdditional analysis of the FFT is found in the homework problems at the end of the chapter.Nevaluations of the sine or cosine,Nmultiplications, andNadditions for each coefficient. There areNcoefficients, so that there must beN^{2}evaluations of the sines and cosines, which uses a lot of computer time. Cooley and Tukey (1965) showed that it is possible to group the data in such a way that the number of multiplications is about (N/2)log_{2}Ninstead ofN^{2}and the sines and cosines need to be evaluated only once, a technique known as thefast Fourier transform(FFT).

The FFT is a famous algorithm in the field of numerical methods. Below is how Press et al. describe it in one of my favorite books, Numerical Recipes.Problem 17. This problem provides some insight into the fast Fourier transform. Start with the expression for anN-point Fourier transform in complex notation,Yin Eq. 11.29a. Show that_{k}Ycan be written as the sum of two_{k}N/2-point Fourier transforms:Y= ½[_{k}Y+_{k}^{e}W^{k}Y], where_{k}^{o}W= exp(-i2π/N), superscriptestands for even values ofj, andostands for odd values.

The discrete Fourier transform can, in fact, be computed inThis process, calledO(Nlog_{2}N) operations with an algorithm called thefast Fourier transform, orFFT. The difference betweenNlog_{2}NandN^{2}is immense. WithN= 10^{6}, for example, it is the difference between, roughly, 30 seconds of CUP time and 2 weeks of CPU time on a microsecond cycle time computer. The existence of an FFT algorithm became generally known only in the mid-1960s, from the work of J. W. Cooley and J. W. Tukey. Retrospectively, we now know…that efficient methods for computing the DFT [discrete Fourier transform] had been independently discovered, and in some cases implemented, by as many as a dozen individuals, starting with Gauss in 1805!

One ‘rediscovery’ of the FFT, that of Danielson and Lanczos in 1942, provides one of the clearest derivations of the algorithm. Danielson and Lanczos showed that a discrete Fourier transform of lengthNcan be rewritten as the sum of two discrete Fourier transforms, each of lengthN/2. One of the two is formed from the even-numbered points of the originalN, the other from the odd-numbered points…

The wonderful thing about theDanielson-Lanczos Lemmais that it can be used recursively. Having reduced the problem of computingFto that of computing_{k}Fand_{k}^{e}F, we can do the same reduction of_{k}^{o}Fto the problem of the transform of its_{k}^{e}N/4 even-numbered input data andN/4 odd-numbered data…

Although there are ways of treating other cases, by far the easiest case is the one in which the originalNis an integer power of 2…With this restriction onN, it is evident that we can continue applying the Danielson-Lanczos Lemma until we have subdivided the data all the way down to transforms of length 1…The points as given are the one-point transforms. We combine adjacent pairs to get two-point transforms, then combine adjacent pairs of pairs to get 4-point transforms, and so on, until the first and second halves of the whole data set are combined into the final transform. Each combination takes on orderNoperations, and there are evidently log_{2}Ncombinations, so the whole algorithm is of orderNlog_{2}N.

*decimation-in-time*, is summarized in this lovely butterfly diagram.