Skip to content

An algorithm for the machine calculation of complex Fourier series

Why this mattered

Cooley and Tukey’s 1965 paper mattered because it made the discrete Fourier transform practically cheap at scale. The direct calculation requires on the order of (N^2) arithmetic operations; their formulation showed how, when (N) is composite and especially when (N = 2^m), the computation can be decomposed into smaller structured pieces requiring on the order of (N \log N) operations. Earlier related ideas existed in the work of Yates, Good, and others, but this paper gave the method in a form directly usable for complex Fourier series on digital computers, including attention to storage and binary-machine implementation. That combination of asymptotic improvement and machine-conscious presentation turned a mathematical rearrangement into a general computational tool.

The practical consequence was that spectral methods moved from being expensive special-purpose calculations to routine numerical operations. Problems in signal processing, radio astronomy, geophysics, crystallography, acoustics, image analysis, numerical solution of differential equations, and statistics could now use Fourier-domain representations on datasets far larger than direct summation would allow. The paper did not merely speed up an existing calculation; it changed what kinds of calculations were feasible, making frequency-domain filtering, convolution via transforms, correlation analysis, and large-scale spectral estimation everyday techniques in scientific computing.

Its longer-term importance lies in how the fast Fourier transform became an enabling primitive for later technologies and discoveries. Modern digital communications, medical imaging, audio and image compression, radar and sonar processing, computational physics, and fast polynomial and integer multiplication all rely on FFT-like decompositions. The paper helped establish a broader lesson of computational science: exploiting algebraic structure can change the effective boundary between possible and impossible. In that sense, the Cooley-Tukey algorithm became not just a faster Fourier method, but one of the central examples of how algorithmic insight can reshape entire scientific and engineering fields.

Abstract

An efficient method for the calculation of the interactions of a 2m factorial experiment was introduced by Yates and is widely known by his name.The generalization to 3m was given by Box et al. [1].Good [2] generalized these methods and gave elegant algorithms for which one class of applications is the calculation of Fourier series.In their full generality, Good's methods are applicable to certain problems in which one must multiply an JV-vector by an JV X N matrix which can be factored into m sparse matrices, where m is proportional to log JV.This results in a procedure requiring a number of operations proportional to JV log JV rather than JV2.These methods are applied here to the calculation of complex Fourier series.They are useful in situations where the number of data points is, or can be chosen to be, a highly composite number.The algorithm is here derived and presented in a rather different form.Attention is given to the choice of JV.It is also shown how special advantage can be obtained in the use of a binary computer with JV = 2m and how the entire calculation can be performed within the array of JV data storage locations used for the given Fourier coefficients.Consider the problem of calculating the complex Fourier series

Sources