
related topics 
{math, number, function} 
{rate, high, increase} 
{system, computer, user} 
{math, energy, light} 
{work, book, publish} 
{company, market, business} 

A fast Fourier transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. There are many distinct FFT algorithms involving a wide range of mathematics, from simple complexnumber arithmetic to group theory and number theory; this article gives an overview of the available techniques and some of their general properties, while the specific algorithms are described in subsidiary articles linked below.
A DFT decomposes a sequence of values into components of different frequencies. This operation is useful in many fields (see discrete Fourier transform for properties and applications of the transform) but computing it directly from the definition is often too slow to be practical. An FFT is a way to compute the same result more quickly: computing a DFT of N points in the naive way, using the definition, takes O(N^{2}) arithmetical operations, while an FFT can compute the same result in only O(N log N) operations. The difference in speed can be substantial, especially for long data sets where N may be in the thousands or millions—in practice, the computation time can be reduced by several orders of magnitude in such cases, and the improvement is roughly proportional to N / log(N). This huge improvement made many DFTbased algorithms practical; FFTs are of great importance to a wide variety of applications, from digital signal processing and solving partial differential equations to algorithms for quick multiplication of large integers.
The most well known FFT algorithms depend upon the factorization of N, but (contrary to popular misconception) there are FFTs with O(N log N) complexity for all N, even for prime N. Many FFT algorithms only depend on the fact that is an Nth primitive root of unity, and thus can be applied to analogous transforms over any finite field, such as numbertheoretic transforms.
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.
Contents
Full article ▸


related documents 
Continued fraction 
Closure (computer science) 
Logarithm 
Axiom of choice 
Tensor product 
Algebraic geometry 
Adjoint functors 
Variable 
Hilbert's tenth problem 
Singleton pattern 
Functional programming 
Dedekind domain 
Orthogonal matrix 
Kolmogorov complexity 
Scheme (programming language) 
Fourier series 
Combinatorics 
Class (computer science) 
Numeral system 
Calculus 
Limit (category theory) 
Design Patterns 
LR parser 
Lie group 
Elliptic curve cryptography 
Binary search tree 
Riemann integral 
Recurrence relation 
Μrecursive function 
Axiom 
