Invention and Engineering
Fast Fourier transform
A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT), or its inverse (IDFT), of a sequence. A Fourier transform converts a signal from its original domain (often time or space) to a representation in the frequency domain and vice versa. The DFT is obtained by decomposing a sequence of values into components of different frequencies. This operation is useful in many fields, but computing it directly from the definition is often too slow to be practical. An FFT rapidly computes such transformations by factorizing the DFT matrix into a product of sparse (mostly zero) factors. As a result, it manages to reduce the complexity of computing the DFT from O ( n 2 ) {\textstyle O(n^{2})} , which arises if one simply applies the definition of DFT, to O ( n log n ) {\textstyle O(n\log n)} , where n is the length of the sequence. The difference in speed can be enormous, especially for long sequences where n may be in the thousands or millions. As the FFT is merely an algebraic refactoring of terms within the DFT, the DFT and the FFT both perform mathematically equivalent and interchangeable operations, assuming that all terms are computed with infinite precision. However, in the presence of round-off error, many FFT algorithms are much more accurate than evaluating the DFT definition directly or indirectly. There are many different FFT algorithms based on a wide range of published theories, from simple complex-number arithmetic to group theory and number theory. The best-known FFT algorithms depend upon the factorization of n, but there are FFTs with O ( n log n ) {\displaystyle O(n\log n)} complexity for all n, including prime values.
Also on this shelf
Hot-bulb engine.
Gift wrapping.
See also
Uncatalogued shelfText from Wikipedia; plate via Wikimedia Commons. Text CC BY-SA 4.0; plate freely licensed (see Commons). Source record. Images and catalogue data are reproduced from open-access collections.