Fast Fourier transform

Fast Fourier transform
source
Name	Fast Fourier transform
Class	Frequency analysis
Data	Complex number
Time	O(n log n)
Space	O(n)
Author	Carl Friedrich Gauss, James Cooley, John Tukey
Year	1805, 1965

Fast Fourier transform. The Fast Fourier transform is a foundational algorithm that efficiently computes the discrete Fourier transform and its inverse, revolutionizing the analysis of digital signals. By decomposing a sequence of values into components of different frequencies, it provides a critical tool for transforming between time and frequency domains. Its development, particularly the 1965 paper by James Cooley and John Tukey, unlocked practical applications across science and engineering, from medical imaging to wireless communication.

Definition and mathematical basis

The algorithm computes the discrete Fourier transform of a sequence, typically representing a sampled signal over time. Mathematically, it transforms n complex numbers into another set of n complex numbers, representing the signal in the frequency domain. This transformation relies on the properties of complex roots of unity, specifically the n-th roots of unity, which allow the decomposition of the DFT sum. The foundational work builds upon principles from Fourier analysis, a field significantly advanced by Joseph Fourier in his study of heat transfer. Efficient computation hinges on the Danielson–Lanczos lemma, which recursively breaks the problem into smaller transforms.

Algorithmic approaches

The most common implementation is the Cooley–Tukey algorithm, which recursively divides the transform size using radices, often a power of two. Another prominent method is the prime-factor algorithm, which handles transform sizes that are coprime by leveraging the Chinese remainder theorem. For real-valued input data, specialized variants like the split-radix FFT offer improved arithmetic efficiency. The Bluestein's algorithm provides a solution for arbitrary n by converting the problem into a convolution, computable via zero-padded transforms. These methods are central to libraries like FFTW and implementations within MATLAB.

Computational complexity

A direct computation of the discrete Fourier transform has a time complexity of O(n²) operations. In contrast, the Fast Fourier transform reduces this to O(n log n), a monumental improvement enabling the processing of large datasets. The exact constant factor depends on the radix and algorithmic optimizations, such as those explored by Stanford University researchers. This efficiency is formally analyzed within the field of computational complexity theory, often referenced in the study of asymptotic computational complexity. The space complexity is typically O(n), though in-place versions minimize additional memory use.

Applications

The algorithm is indispensable in digital signal processing for audio and image compression, forming the core of standards like MP3 and JPEG. In telecommunications, it is crucial for orthogonal frequency-division multiplexing used in Wi-Fi and 4G networks. Scientific applications include spectroscopy at facilities like CERN and magnetic resonance imaging in hospitals. It also accelerates computations in computational fluid dynamics and quantum chemistry, and is fundamental to modern cryptanalysis and error-correcting code design. The SETI Institute employs similar transforms in the search for extraterrestrial intelligence.

History and development

While the modern algorithm is attributed to James Cooley and John Tukey in 1965, historical evidence shows Carl Friedrich Gauss derived a similar method around 1805 while analyzing asteroid orbits. The 20th century saw independent rediscoveries, including work by Danielson and Lanczos during the Manhattan Project. The publication in Mathematics of Computation coincided with the advent of the IBM System/360, enabling widespread adoption. Subsequent refinements came from institutions like MIT and Bell Labs, with Winograd developing minimal multiplication algorithms. The algorithm's impact was recognized by the IEEE, which awarded the IEEE Medal of Honor to related pioneers.

Category:Numerical analysis Category:Signal processing Category:Algorithms