Fast Fourier transform

A fast Fourier transform (FFT) is an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> that computes the <a href="/facts/Discrete_Fourier_transform/uK9Tjsbl">discrete Fourier transform</a> (DFT) of a sequence, or its inverse (IDFT). A <a href="/facts/Fourier_transform/XXhKJtc8">Fourier transform</a> converts a signal from its original domain (often time or space) to a representation in the <a href="/facts/Frequency_domain/pyTVrUSq">frequency domain</a> and vice versa.
The DFT is obtained by decomposing a <a href="/facts/Sequence/gV2S4uqp">sequence</a> 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 <a href="/facts/Matrix_decomposition/xVBnAg0x">factorizing</a> the <a href="/facts/DFT_matrix/oQM4frPU">DFT matrix</a> into a product of <a href="/facts/Sparse_matrix/FFtN0XjR">sparse</a> (mostly zero) factors. As a result, it manages to reduce the <a href="/facts/Computational_complexity_theory/etHuVF3U">complexity</a> 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 data size. The difference in speed can be enormous, especially for long data sets where n may be in the thousands or millions.
As the FFT is merely an algebraic refactoring of terms within the DFT, then 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 <a href="/facts/Round-off_error/aF9N8X4I">round-off error</a>, many FFT algorithms are much more accurate than evaluating the DFT definition directly or indirectly.

Fast Fourier transforms are widely used for <a href="/facts/Discrete_Fourier_transform/uK9Tjsbl">applications</a> in engineering, music, science, and mathematics. The basic ideas were popularized in 1965, but some algorithms had been derived as early as 1805. In 1994, <a href="/facts/Gilbert_Strang/bbzaoPsm">Gilbert Strang</a> described the FFT as "the most important <a href="/facts/Numerical_algorithm/QT9cYa9z">numerical algorithm</a> of our lifetime", and it was included in Top 10 Algorithms of 20th Century by the <a href="/facts/IEEE/UddC4pUW">IEEE</a> magazine Computing in Science & Engineering.
There are many different FFT algorithms based on a wide range of published theories, from simple <a href="/facts/Complex_number/2w7mqI7e">complex-number arithmetic</a> to <a href="/facts/Group_theory/NfowcI5H">group theory</a> and <a href="/facts/Number_theory/zhoa7zrc">number theory</a>. The best-known FFT algorithms depend upon the <a href="/facts/Factorization/tXrBXFh1">factorization</a> of n, but there are FFTs with 
 
 
 
 O
 (
 n
 log
 ⁡
 n
 )
 
 
 {\displaystyle O(n\log n)}
 
 complexity for all, even <a href="/facts/Prime/L20FLkgn">prime</a>, n. Many FFT algorithms depend only on the fact that 
 
 
 
 
 e
 
 −
 2
 π
 i
 
 /
 
 n
 
 
 
 
 {\textstyle e^{-2\pi i/n}}
 
 is an nth <a href="/facts/Primitive_root_of_unity/EqH0ho1Y">primitive root of unity</a>, and thus can be applied to analogous transforms over any <a href="/facts/Finite_field/UkMGJo3m">finite field</a>, such as <a href="/facts/Number-theoretic_transform/ntR67BjE">number-theoretic transforms</a>. Since the inverse DFT is the same as the DFT, but with the opposite sign in the exponent and a 1/n factor, any FFT algorithm can easily be adapted for it.

Fast Fourier transform open-in-new

Fast Fourier transform