HOME

TheInfoList



OR:

A fast Fourier transform (FFT) is an
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
that computes the
discrete Fourier transform In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a comple ...
(DFT) of a sequence, or its inverse (IDFT).
Fourier analysis In mathematics, Fourier analysis () is the study of the way general functions may be represented or approximated by sums of simpler trigonometric functions. Fourier analysis grew from the study of Fourier series, and is named after Joseph ...
converts a signal from its original domain (often time or space) to a representation in the
frequency domain In physics, electronics, control systems engineering, and statistics, the frequency domain refers to the analysis of mathematical functions or signals with respect to frequency, rather than time. Put simply, a time-domain graph shows how a s ...
and vice versa. The DFT is obtained by decomposing a
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called ...
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 Complexity characterises the behaviour of a system or model whose components interact in multiple ways and follow local rules, leading to nonlinearity, randomness, collective dynamics, hierarchy, and emergence. The term is generally used to ch ...
of computing the DFT from O\left(N^2\right), which arises if one simply applies the definition of DFT, to 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. In the presence of
round-off error A roundoff error, also called rounding error, is the difference between the result produced by a given algorithm using exact arithmetic and the result produced by the same algorithm using finite-precision, rounded arithmetic. Rounding errors are d ...
, 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 In abstract algebra, group theory studies the algebraic structures known as groups. The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces, can all be seen ...
and
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Ma ...
. Fast Fourier transforms are widely used for
applications Application may refer to: Mathematics and computing * Application software, computer software designed to help the user to perform specific tasks ** Application layer, an abstraction layer that specifies protocols and interface methods used in a c ...
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, Gilbert Strang described the FFT as "the most important
numerical algorithm Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of numerical methods ...
of our lifetime", and it was included in Top 10 Algorithms of 20th Century by the
IEEE The Institute of Electrical and Electronics Engineers (IEEE) is a 501(c)(3) professional association for electronic engineering and electrical engineering (and associated disciplines) with its corporate office in New York City and its operati ...
magazine ''Computing in Science & Engineering''. The best-known FFT algorithms depend upon the
factorization In mathematics, factorization (or factorisation, see English spelling differences) or factoring consists of writing a number or another mathematical object as a product of several ''factors'', usually smaller or simpler objects of the same kind ...
of ''N'', but there are FFTs with O(''N'' log ''N'')
complexity Complexity characterises the behaviour of a system or model whose components interact in multiple ways and follow local rules, leading to nonlinearity, randomness, collective dynamics, hierarchy, and emergence. The term is generally used to ch ...
for all ''N'', even for
prime A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
 ''N''. Many FFT algorithms depend only on the fact that e^ is an ''N''-th
primitive root of unity In mathematics, a root of unity, occasionally called a de Moivre number, is any complex number that yields 1 when raised to some positive integer power . Roots of unity are used in many branches of mathematics, and are especially important in ...
, and thus can be applied to analogous transforms over any
finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
, such as
number-theoretic transform In mathematics, the discrete Fourier transform over a ring generalizes the discrete Fourier transform (DFT), of a function whose values are commonly complex numbers, over an arbitrary ring. Definition Let R be any ring, let n\geq 1 be an intege ...
s. 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.


History

The development of fast algorithms for DFT can be traced to
Carl Friedrich Gauss Johann Carl Friedrich Gauss (; german: Gauß ; la, Carolus Fridericus Gauss; 30 April 177723 February 1855) was a German mathematician and physicist who made significant contributions to many fields in mathematics and science. Sometimes refer ...
's unpublished work in 1805 when he needed it to interpolate the orbit of asteroids
Pallas Pallas may refer to: Astronomy * 2 Pallas asteroid ** Pallas family, a group of asteroids that includes 2 Pallas * Pallas (crater), a crater on Earth's moon Mythology * Pallas (Giant), a son of Uranus and Gaia, killed and flayed by Athena * Pa ...
and Juno from sample observations. His method was very similar to the one published in 1965 by
James Cooley James William Cooley (1926 – June 29, 2016) was an American mathematician. Cooley received a B.A. degree in 1949 from Manhattan College, Bronx, NY, an M.A. degree in 1951 from Columbia University, New York, NY, and a Ph.D. degree in 1961 in appl ...
and
John Tukey John Wilder Tukey (; June 16, 1915 – July 26, 2000) was an American mathematician and statistician, best known for the development of the fast Fourier Transform (FFT) algorithm and box plot. The Tukey range test, the Tukey lambda distributi ...
, who are generally credited for the invention of the modern generic FFT algorithm. While Gauss's work predated even
Joseph Fourier Jean-Baptiste Joseph Fourier (; ; 21 March 1768 – 16 May 1830) was a French mathematician and physicist born in Auxerre and best known for initiating the investigation of Fourier series, which eventually developed into Fourier analysis and ha ...
's results in 1822, he did not analyze the computation time and eventually used other methods to achieve his goal. Between 1805 and 1965, some versions of FFT were published by other authors.
Frank Yates Frank Yates FRS (12 May 1902 – 17 June 1994) was one of the pioneers of 20th-century statistics. Biography Yates was born in Manchester, England, the eldest of five children (and only son) of seed merchant Percy Yates and his wife Edith. ...
in 1932 published his version called ''interaction algorithm'', which provided efficient computation of Hadamard and Walsh transforms. Yates' algorithm is still used in the field of statistical design and analysis of experiments. In 1942, G. C. Danielson and
Cornelius Lanczos __NOTOC__ Cornelius (Cornel) Lanczos ( hu, Lánczos Kornél, ; born as Kornél Lőwy, until 1906: ''Löwy (Lőwy) Kornél''; February 2, 1893 – June 25, 1974) was a Hungarian-American and later Hungarian-Irish mathematician and physicist. Acco ...
published their version to compute DFT for
x-ray crystallography X-ray crystallography is the experimental science determining the atomic and molecular structure of a crystal, in which the crystalline structure causes a beam of incident X-rays to diffract into many specific directions. By measuring the angles ...
, a field where calculation of Fourier transforms presented a formidable bottleneck. While many methods in the past had focused on reducing the constant factor for O\left(N^2\right) computation by taking advantage of "symmetries", Danielson and Lanczos realized that one could use the "periodicity" and apply a "doubling trick" to "double /nowiki> with only slightly more than double the labor", though like Gauss they did not analyze that this led to O(N \log N) scaling. James Cooley and John Tukey independently rediscovered these earlier algorithms and published a more general FFT in 1965 that is applicable when ''N'' is composite and not necessarily a power of 2, as well as analyzing the O(N \log N) scaling. Tukey came up with the idea during a meeting of
President Kennedy John Fitzgerald Kennedy (May 29, 1917 – November 22, 1963), often referred to by his initials JFK and the nickname Jack, was an American politician who served as the 35th president of the United States from 1961 until assassination of Joh ...
's Science Advisory Committee where a discussion topic involved detecting nuclear tests by the Soviet Union by setting up sensors to surround the country from outside. To analyze the output of these sensors, an FFT algorithm would be needed. In discussion with Tukey,
Richard Garwin Richard Lawrence Garwin (born April 19, 1928) is an American physicist, best known as the author of the first hydrogen bomb design. In 1978, Garwin was elected a member of the National Academy of Engineering for contributing to the application ...
recognized the general applicability of the algorithm not just to national security problems, but also to a wide range of problems including one of immediate interest to him, determining the periodicities of the spin orientations in a 3-D crystal of Helium-3. Garwin gave Tukey's idea to Cooley (both worked at IBM's Watson labs) for implementation. Cooley and Tukey published the paper in a relatively short time of six months. As Tukey did not work at IBM, the patentability of the idea was doubted and the algorithm went into the public domain, which, through the computing revolution of the next decade, made FFT one of the indispensable algorithms in
digital signal processing Digital signal processing (DSP) is the use of digital processing, such as by computers or more specialized digital signal processors, to perform a wide variety of signal processing operations. The digital signals processed in this manner are ...
.


Definition

Let x_0, …, x_ be
complex number In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the fo ...
s. The DFT is defined by the formula : X_k = \sum_^ x_n e^ \qquad k = 0,\ldots,N-1, where e^ is a primitive th root of 1. Evaluating this definition directly requires O\left(N^2\right) operations: there are ''N'' outputs ''X''''k'', and each output requires a sum of ''N'' terms. An FFT is any method to compute the same results in O(N \log N) operations. All known FFT algorithms require \Theta(N \log N) operations, although there is no known proof that lower complexity is impossible. To illustrate the savings of an FFT, consider the count of complex multiplications and additions for N=4096 data points. Evaluating the DFT's sums directly involves N^2 complex multiplications and N(N-1) complex additions, of which O(N) operations can be saved by eliminating trivial operations such as multiplications by 1, leaving about 30 million operations. In contrast, the radix-2 Cooley–Tukey algorithm, for ''N'' a power of 2, can compute the same result with only (N/2)\log_2(N) complex multiplications (again, ignoring simplifications of multiplications by 1 and similar) and N\log_2(N) complex additions, in total about 30,000 operations — a thousand times less than with direct evaluation. In practice, actual performance on modern computers is usually dominated by factors other than the speed of arithmetic operations and the analysis is a complicated subject (for example, see Frigo &
Johnson Johnson is a surname of Anglo-Norman origin meaning "Son of John". It is the second most common in the United States and 154th most common in the world. As a common family name in Scotland, Johnson is occasionally a variation of ''Johnston'', a ...
, 2005), but the overall improvement from O\left(N^2\right) to O(N \log N) remains.


Algorithms


Cooley–Tukey algorithm

By far the most commonly used FFT is the Cooley–Tukey algorithm. This is a
divide-and-conquer algorithm In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved dire ...
that
recursively Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
breaks down a DFT of any
composite Composite or compositing may refer to: Materials * Composite material, a material that is made from several different substances ** Metal matrix composite, composed of metal and other parts ** Cermet, a composite of ceramic and metallic materials ...
size N = N_1N_2 into many smaller DFTs of sizes N_1 and N_2, along with O(N) multiplications by complex
roots of unity In mathematics, a root of unity, occasionally called a de Moivre number, is any complex number that yields 1 when raised to some positive integer power . Roots of unity are used in many branches of mathematics, and are especially important in ...
traditionally called twiddle factors (after Gentleman and Sande, 1966). This method (and the general idea of an FFT) was popularized by a publication of Cooley and Tukey in 1965, but it was later discovered that those two authors had independently re-invented an algorithm known to
Carl Friedrich Gauss Johann Carl Friedrich Gauss (; german: Gauß ; la, Carolus Fridericus Gauss; 30 April 177723 February 1855) was a German mathematician and physicist who made significant contributions to many fields in mathematics and science. Sometimes refer ...
around 1805 (and subsequently rediscovered several times in limited forms). The best known use of the Cooley–Tukey algorithm is to divide the transform into two pieces of size ''N''/2 at each step, and is therefore limited to power-of-two sizes, but any factorization can be used in general (as was known to both Gauss and Cooley/Tukey). These are called the ''radix-2'' and ''mixed-radix'' cases, respectively (and other variants such as the split-radix FFT have their own names as well). Although the basic idea is recursive, most traditional implementations rearrange the algorithm to avoid explicit recursion. Also, because the Cooley–Tukey algorithm breaks the DFT into smaller DFTs, it can be combined arbitrarily with any other algorithm for the DFT, such as those described below.


Other FFT algorithms

There are FFT algorithms other than Cooley–Tukey. For ''N'' = ''N''1''N''2 with
coprime In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
''N''1 and ''N''2, one can use the prime-factor (Good–Thomas) algorithm (PFA), based on the
Chinese remainder theorem In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of the ...
, to factorize the DFT similarly to Cooley–Tukey but without the twiddle factors. The Rader–Brenner algorithm (1976) is a Cooley–Tukey-like factorization but with purely imaginary twiddle factors, reducing multiplications at the cost of increased additions and reduced
numerical stability In the mathematical subfield of numerical analysis, numerical stability is a generally desirable property of numerical algorithms. The precise definition of stability depends on the context. One is numerical linear algebra and the other is algori ...
; it was later superseded by the split-radix variant of Cooley–Tukey (which achieves the same multiplication count but with fewer additions and without sacrificing accuracy). Algorithms that recursively factorize the DFT into smaller operations other than DFTs include the Bruun and QFT algorithms. (The Rader–Brenner and QFT algorithms were proposed for power-of-two sizes, but it is possible that they could be adapted to general composite ''N''. Bruun's algorithm applies to arbitrary even composite sizes.) Bruun's algorithm, in particular, is based on interpreting the FFT as a recursive factorization of the
polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exampl ...
''z''''N'' − 1, here into real-coefficient polynomials of the form ''z''''M'' − 1 and ''z''2''M'' + ''az''''M'' + 1. Another polynomial viewpoint is exploited by the Winograd FFT algorithm, which factorizes ''z''''N'' − 1 into
cyclotomic polynomial In mathematics, the ''n''th cyclotomic polynomial, for any positive integer ''n'', is the unique irreducible polynomial with integer coefficients that is a divisor of x^n-1 and is not a divisor of x^k-1 for any Its roots are all ''n''th primitiv ...
s—these often have coefficients of 1, 0, or −1, and therefore require few (if any) multiplications, so Winograd can be used to obtain minimal-multiplication FFTs and is often used to find efficient algorithms for small factors. Indeed, Winograd showed that the DFT can be computed with only O(''N'') irrational multiplications, leading to a proven achievable lower bound on the number of multiplications for power-of-two sizes; unfortunately, this comes at the cost of many more additions, a tradeoff no longer favorable on modern
processors A central processing unit (CPU), also called a central processor, main processor or just processor, is the electronic circuitry that executes instructions comprising a computer program. The CPU performs basic arithmetic, logic, controlling, a ...
with hardware multipliers. In particular, Winograd also makes use of the PFA as well as an algorithm by Rader for FFTs of ''prime'' sizes. Rader's algorithm, exploiting the existence of a generator for the multiplicative
group A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic ide ...
modulo prime ''N'', expresses a DFT of prime size ''N'' as a cyclic
convolution In mathematics (in particular, functional analysis), convolution is a mathematical operation on two functions ( and ) that produces a third function (f*g) that expresses how the shape of one is modified by the other. The term ''convolution'' ...
of (composite) size ''N'' − 1, which can then be computed by a pair of ordinary FFTs via the
convolution theorem In mathematics, the convolution theorem states that under suitable conditions the Fourier transform of a convolution of two functions (or signals) is the pointwise product of their Fourier transforms. More generally, convolution in one domain (e.g ...
(although Winograd uses other convolution methods). Another prime-size FFT is due to L. I. Bluestein, and is sometimes called the
chirp-z algorithm The chirp Z-transform (CZT) is a generalization of the discrete Fourier transform (DFT). While the DFT samples the Z plane at uniformly-spaced points along the unit circle, the chirp Z-transform samples along spiral arcs in the Z-plane, correspon ...
; it also re-expresses a DFT as a convolution, but this time of the ''same'' size (which can be zero-padded to a
power of two A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer  as the exponent. In a context where only integers are considered, is restricted to non-negat ...
and evaluated by radix-2 Cooley–Tukey FFTs, for example), via the identity : nk = -\frac 2 + \frac 2 + \frac 2. Hexagonal fast Fourier transform (HFFT) aims at computing an efficient FFT for the hexagonally-sampled data by using a new addressing scheme for hexagonal grids, called Array Set Addressing (ASA).


FFT algorithms specialized for real or symmetric data

In many applications, the input data for the DFT are purely real, in which case the outputs satisfy the symmetry :X_ = X_k^* and efficient FFT algorithms have been designed for this situation (see e.g. Sorensen, 1987). One approach consists of taking an ordinary algorithm (e.g. Cooley–Tukey) and removing the redundant parts of the computation, saving roughly a factor of two in time and memory. Alternatively, it is possible to express an ''even''-length real-input DFT as a complex DFT of half the length (whose real and imaginary parts are the even/odd elements of the original real data), followed by O(''N'') post-processing operations. It was once believed that real-input DFTs could be more efficiently computed by means of the discrete Hartley transform (DHT), but it was subsequently argued that a specialized real-input DFT algorithm (FFT) can typically be found that requires fewer operations than the corresponding DHT algorithm (FHT) for the same number of inputs. Bruun's algorithm (above) is another method that was initially proposed to take advantage of real inputs, but it has not proved popular. There are further FFT specializations for the cases of real data that have even/odd symmetry, in which case one can gain another factor of roughly two in time and memory and the DFT becomes the
discrete cosine Discrete may refer to: *Discrete particle or quantum in physics, for example in quantum theory * Discrete device, an electronic component with just one circuit element, either passive or active, other than an integrated circuit * Discrete group, a ...
/ sine transform(s) ( DCT/ DST). Instead of directly modifying an FFT algorithm for these cases, DCTs/DSTs can also be computed via FFTs of real data combined with O(''N'') pre- and post-processing.


Computational issues


Bounds on complexity and operation counts

A fundamental question of longstanding theoretical interest is to prove lower bounds on the
complexity Complexity characterises the behaviour of a system or model whose components interact in multiple ways and follow local rules, leading to nonlinearity, randomness, collective dynamics, hierarchy, and emergence. The term is generally used to ch ...
and exact operation counts of fast Fourier transforms, and many open problems remain. It is not rigorously proved whether DFTs truly require \Omega(N \log N) (i.e., order ''N \log N'' or greater) operations, even for the simple case of
power of two A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer  as the exponent. In a context where only integers are considered, is restricted to non-negat ...
sizes, although no algorithms with lower complexity are known. In particular, the count of arithmetic operations is usually the focus of such questions, although actual performance on modern-day computers is determined by many other factors such as
cache Cache, caching, or caché may refer to: Places United States * Cache, Idaho, an unincorporated community * Cache, Illinois, an unincorporated community * Cache, Oklahoma, a city in Comanche County * Cache, Utah, Cache County, Utah * Cache County ...
or CPU pipeline optimization. Following work by
Shmuel Winograd __NOTOC__ Shmuel Winograd ( he, שמואל וינוגרד; January 4, 1936 – March 25, 2019) was an Israeli-American computer scientist, noted for his contributions to computational complexity. He has proved several major results regarding the ...
(1978), a tight Θ(''N'') lower bound is known for the number of real multiplications required by an FFT. It can be shown that only 4N - 2\log_2^2(N) - 2\log_2(N) - 4 irrational real multiplications are required to compute a DFT of power-of-two length N = 2^m. Moreover, explicit algorithms that achieve this count are known (Heideman &
Burrus ''Burrus'' is a genus of shield bugs in the tribe Podopini Podopinae, known as turtle bugs, are a subfamily of the insect family Pentatomidae. The type genus is ''Podops''. Tribes and Genera ''BioLib'' lists: Brachycerocorini Auth. Davidova ...
, 1986; Duhamel, 1990). However, these algorithms require too many additions to be practical, at least on modern computers with hardware multipliers (Duhamel, 1990; Frigo &
Johnson Johnson is a surname of Anglo-Norman origin meaning "Son of John". It is the second most common in the United States and 154th most common in the world. As a common family name in Scotland, Johnson is occasionally a variation of ''Johnston'', a ...
, 2005). A tight lower bound is not known on the number of required additions, although lower bounds have been proved under some restrictive assumptions on the algorithms. In 1973, Morgenstern proved an \Omega(N \log N) lower bound on the addition count for algorithms where the multiplicative constants have bounded magnitudes (which is true for most but not all FFT algorithms). Pan (1986) proved an \Omega(N \log N) lower bound assuming a bound on a measure of the FFT algorithm's "asynchronicity", but the generality of this assumption is unclear. For the case of power-of-two ''N'', Papadimitriou (1979) argued that the number N \log_2 N of complex-number additions achieved by Cooley–Tukey algorithms is ''optimal'' under certain assumptions on the
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...
of the algorithm (his assumptions imply, among other things, that no additive identities in the roots of unity are exploited). (This argument would imply that at least 2N \log_2 N real additions are required, although this is not a tight bound because extra additions are required as part of complex-number multiplications.) Thus far, no published FFT algorithm has achieved fewer than N \log_2 N complex-number additions (or their equivalent) for power-of-two ''N''. A third problem is to minimize the ''total'' number of real multiplications and additions, sometimes called the "arithmetic complexity" (although in this context it is the exact count and not the asymptotic complexity that is being considered). Again, no tight lower bound has been proven. Since 1968, however, the lowest published count for power-of-two ''N'' was long achieved by the
split-radix FFT algorithm The split-radix FFT is a fast Fourier transform (FFT) algorithm for computing the discrete Fourier transform (DFT), and was first described in an initially little-appreciated paper by R. Yavne (1968) and subsequently rediscovered simultaneously by ...
, which requires 4N\log_2(N) - 6N + 8 real multiplications and additions for ''N'' > 1. This was recently reduced to \sim \frac N \log_2 N (Johnson and Frigo, 2007; Lundy and Van Buskirk, 2007). A slightly larger count (but still better than split radix for ''N'' ≥ 256) was shown to be provably optimal for ''N'' ≤ 512 under additional restrictions on the possible algorithms (split-radix-like flowgraphs with unit-modulus multiplicative factors), by reduction to a
satisfiability modulo theories In computer science and mathematical logic, satisfiability modulo theories (SMT) is the problem of determining whether a mathematical formula is satisfiable. It generalizes the Boolean satisfiability problem (SAT) to more complex formulas involvi ...
problem solvable by
brute force Brute Force or brute force may refer to: Techniques * Brute force method or proof by exhaustion, a method of mathematical proof * Brute-force attack, a cryptanalytic attack * Brute-force search, a computer problem-solving technique People * Brut ...
(Haynal & Haynal, 2011). Most of the attempts to lower or prove the complexity of FFT algorithms have focused on the ordinary complex-data case, because it is the simplest. However, complex-data FFTs are so closely related to algorithms for related problems such as real-data FFTs, discrete cosine transforms, discrete Hartley transforms, and so on, that any improvement in one of these would immediately lead to improvements in the others (Duhamel & Vetterli, 1990).


Approximations

All of the FFT algorithms discussed above compute the DFT exactly (i.e. neglecting
floating-point In computing, floating-point arithmetic (FP) is arithmetic that represents real numbers approximately, using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. For example, 12.345 can ...
errors). A few "FFT" algorithms have been proposed, however, that compute the DFT ''approximately'', with an error that can be made arbitrarily small at the expense of increased computations. Such algorithms trade the approximation error for increased speed or other properties. For example, an approximate FFT algorithm by Edelman et al. (1999) achieves lower communication requirements for
parallel computing Parallel computing is a type of computation in which many calculations or processes are carried out simultaneously. Large problems can often be divided into smaller ones, which can then be solved at the same time. There are several different f ...
with the help of a
fast multipole method __NOTOC__ The fast multipole method (FMM) is a numerical technique that was developed to speed up the calculation of long-ranged forces in the ''n''-body problem. It does this by expanding the system Green's function using a multipole expansion, w ...
. A
wavelet A wavelet is a wave-like oscillation with an amplitude that begins at zero, increases or decreases, and then returns to zero one or more times. Wavelets are termed a "brief oscillation". A taxonomy of wavelets has been established, based on the num ...
-based approximate FFT by Guo and Burrus (1996) takes sparse inputs/outputs (time/frequency localization) into account more efficiently than is possible with an exact FFT. Another algorithm for approximate computation of a subset of the DFT outputs is due to Shentov et al. (1995). The Edelman algorithm works equally well for sparse and non-sparse data, since it is based on the compressibility (rank deficiency) of the Fourier matrix itself rather than the compressibility (sparsity) of the data. Conversely, if the data are sparse—that is, if only ''K'' out of ''N'' Fourier coefficients are nonzero—then the complexity can be reduced to O(''K''log(''N'')log(''N''/''K'')), and this has been demonstrated to lead to practical speedups compared to an ordinary FFT for ''N''/''K'' > 32 in a large-''N'' example (''N'' = 222) using a probabilistic approximate algorithm (which estimates the largest ''K'' coefficients to several decimal places).


Accuracy

FFT algorithms have errors when finite-precision floating-point arithmetic is used, but these errors are typically quite small; most FFT algorithms, e.g. Cooley–Tukey, have excellent numerical properties as a consequence of the
pairwise summation In numerical analysis, pairwise summation, also called cascade summation, is a technique to sum a sequence of finite- precision floating-point numbers that substantially reduces the accumulated round-off error compared to naively accumulating the s ...
structure of the algorithms. The upper bound on the
relative error The approximation error in a data value is the discrepancy between an exact value and some ''approximation'' to it. This error can be expressed as an absolute error (the numerical amount of the discrepancy) or as a relative error (the absolute er ...
for the Cooley–Tukey algorithm is O(\epsilon \log N), compared to O(\epsilon N^) for the naïve DFT formula, where ε is the machine floating-point relative precision. In fact, the
root mean square In mathematics and its applications, the root mean square of a set of numbers x_i (abbreviated as RMS, or rms and denoted in formulas as either x_\mathrm or \mathrm_x) is defined as the square root of the mean square (the arithmetic mean of the ...
(rms) errors are much better than these upper bounds, being only O(\epsilon \sqrt) for Cooley–Tukey and O(\epsilon \sqrt) for the naïve DFT (Schatzman, 1996). These results, however, are very sensitive to the accuracy of the twiddle factors used in the FFT (i.e. the
trigonometric function In mathematics, the trigonometric functions (also called circular functions, angle functions or goniometric functions) are real functions which relate an angle of a right-angled triangle to ratios of two side lengths. They are widely used in a ...
values), and it is not unusual for incautious FFT implementations to have much worse accuracy, e.g. if they use inaccurate trigonometric recurrence formulas. Some FFTs other than Cooley–Tukey, such as the Rader–Brenner algorithm, are intrinsically less stable. In
fixed-point arithmetic In computing, fixed-point is a method of representing fractional (non-integer) numbers by storing a fixed number of digits of their fractional part. Dollar amounts, for example, are often stored with exactly two fractional digits, represent ...
, the finite-precision errors accumulated by FFT algorithms are worse, with rms errors growing as O(\sqrt) for the Cooley–Tukey algorithm (Welch, 1969). Achieving this accuracy requires careful attention to scaling to minimize loss of precision, and fixed-point FFT algorithms involve rescaling at each intermediate stage of decompositions like Cooley–Tukey. To verify the correctness of an FFT implementation, rigorous guarantees can be obtained in O(N \log N) time by a simple procedure checking the linearity, impulse-response, and time-shift properties of the transform on random inputs (Ergün, 1995).


Multidimensional FFTs

As defined in the multidimensional DFT article, the multidimensional DFT :X_\mathbf = \sum_^ e^ x_\mathbf transforms an array ''x''n with a ''d''-dimensional
vector Vector most often refers to: *Euclidean vector, a quantity with a magnitude and a direction *Vector (epidemiology), an agent that carries and transmits an infectious pathogen into another living organism Vector may also refer to: Mathematic ...
of indices \mathbf = \left(n_1, \ldots, n_d\right) by a set of ''d'' nested summations (over n_j = 0 \ldots N_j - 1 for each ''j''), where the division n/N, defined as \mathbf / \mathbf = \left(n_1/N_1, \ldots, n_d/N_d\right), is performed element-wise. Equivalently, it is the composition of a sequence of ''d'' sets of one-dimensional DFTs, performed along one dimension at a time (in any order). This compositional viewpoint immediately provides the simplest and most common multidimensional DFT algorithm, known as the row-column algorithm (after the two-dimensional case, below). That is, one simply performs a sequence of ''d'' one-dimensional FFTs (by any of the above algorithms): first you transform along the ''n''1 dimension, then along the ''n''2 dimension, and so on (or actually, any ordering works). This method is easily shown to have the usual O(N \log N) complexity, where N = N_1 \cdot N_2 \cdot \cdots \cdot N_d is the total number of data points transformed. In particular, there are ''N''/''N''1 transforms of size ''N''1, etcetera, so the complexity of the sequence of FFTs is: :\begin & \frac O(N_1 \log N_1) + \cdots + \frac O(N_d \log N_d) \\ pt = & O\left(N \left log N_1 + \cdots + \log N_d\rightright) = O(N \log N). \end In two dimensions, the ''x''k can be viewed as an n_1 \times n_2
matrix Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** '' The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchi ...
, and this algorithm corresponds to first performing the FFT of all the rows (resp. columns), grouping the resulting transformed rows (resp. columns) together as another n_1 \times n_2 matrix, and then performing the FFT on each of the columns (resp. rows) of this second matrix, and similarly grouping the results into the final result matrix. In more than two dimensions, it is often advantageous for
cache Cache, caching, or caché may refer to: Places United States * Cache, Idaho, an unincorporated community * Cache, Illinois, an unincorporated community * Cache, Oklahoma, a city in Comanche County * Cache, Utah, Cache County, Utah * Cache County ...
locality to group the dimensions recursively. For example, a three-dimensional FFT might first perform two-dimensional FFTs of each planar "slice" for each fixed ''n''1, and then perform the one-dimensional FFTs along the ''n''1 direction. More generally, an
asymptotically optimal In computer science, an algorithm is said to be asymptotically optimal if, roughly speaking, for large inputs it performs at worst a constant factor (independent of the input size) worse than the best possible algorithm. It is a term commonly en ...
cache-oblivious algorithm In computing, a cache-oblivious algorithm (or cache-transcendent algorithm) is an algorithm designed to take advantage of a processor cache without having the size of the cache (or the length of the cache lines, etc.) as an explicit parameter. An ...
consists of recursively dividing the dimensions into two groups (n_1, \ldots, n_) and (n_, \ldots, n_d) that are transformed recursively (rounding if ''d'' is not even) (see Frigo and Johnson, 2005). Still, this remains a straightforward variation of the row-column algorithm that ultimately requires only a one-dimensional FFT algorithm as the base case, and still has O(''N'' log ''N'') complexity. Yet another variation is to perform matrix transpositions in between transforming subsequent dimensions, so that the transforms operate on contiguous data; this is especially important for out-of-core and
distributed memory In computer science, distributed memory refers to a multiprocessor computer system in which each processor has its own private memory. Computational tasks can only operate on local data, and if remote data are required, the computational task mu ...
situations where accessing non-contiguous data is extremely time-consuming. There are other multidimensional FFT algorithms that are distinct from the row-column algorithm, although all of them have O(N \log N) complexity. Perhaps the simplest non-row-column FFT is the
vector-radix FFT algorithm The vector-radix FFT algorithm, is a multidimensional fast Fourier transform (FFT) algorithm, which is a generalization of the ordinary Cooley–Tukey FFT algorithm that divides the transform dimensions by arbitrary radices. It breaks a multidimensi ...
, which is a generalization of the ordinary Cooley–Tukey algorithm where one divides the transform dimensions by a vector \mathbf = \left(r_1, r_2, \ldots, r_d\right) of radices at each step. (This may also have cache benefits.) The simplest case of vector-radix is where all of the radices are equal (e.g. vector-radix-2 divides ''all'' of the dimensions by two), but this is not necessary. Vector radix with only a single non-unit radix at a time, i.e. \mathbf = \left(1, \ldots, 1, r, 1, \ldots, 1\right), is essentially a row-column algorithm. Other, more complicated, methods include polynomial transform algorithms due to Nussbaumer (1977), which view the transform in terms of convolutions and polynomial products. See Duhamel and Vetterli (1990) for more information and references.


Other generalizations

An O(N^ \log N) generalization to
spherical harmonics In mathematics and physical science, spherical harmonics are special functions defined on the surface of a sphere. They are often employed in solving partial differential equations in many scientific fields. Since the spherical harmonics form ...
on the sphere ''S''2 with ''N''2 nodes was described by Mohlenkamp, along with an algorithm conjectured (but not proven) to have O(N^2 \log^2(N)) complexity; Mohlenkamp also provides an implementation in the libftsh library. A spherical-harmonic algorithm with O(N^2 \log N)complexity is described by Rokhlin and Tygert. The
fast folding algorithm In signal processing, the fast folding algorithm (Staelin, 1969) is an efficient algorithm for the detection of approximately- periodic events within time series data. It computes superpositions of the signal modulo various window sizes simultaneou ...
is analogous to the FFT, except that it operates on a series of binned waveforms rather than a series of real or complex scalar values. Rotation (which in the FFT is multiplication by a complex phasor) is a circular shift of the component waveform. Various groups have also published "FFT" algorithms for non-equispaced data, as reviewed in Potts ''et al.'' (2001). Such algorithms do not strictly compute the DFT (which is only defined for equispaced data), but rather some approximation thereof (a non-uniform discrete Fourier transform, or NDFT, which itself is often computed only approximately). More generally there are various other methods of
spectral estimation In statistical signal processing, the goal of spectral density estimation (SDE) or simply spectral estimation is to estimate the spectral density (also known as the power spectral density) of a signal from a sequence of time samples of the signa ...
.


Applications

The FFT is used in digital recording, sampling,
additive synthesis Additive synthesis is a sound synthesis technique that creates timbre by adding sine waves together. The timbre of musical instruments can be considered in the light of Fourier theory to consist of multiple harmonic or inharmonic '' partials'' ...
and pitch correction software. The FFT's importance derives from the fact that it has made working in the frequency domain equally computationally feasible as working in the temporal or spatial domain. Some of the important applications of the FFT include: * fast large-integer
multiplication algorithm A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are more efficient than others. Efficient multiplication algorithms have existed since the advent of the d ...
s and polynomial multiplication, * efficient matrix–vector multiplication for Toeplitz, circulant and other structured matrices, * filtering algorithms (see overlap–add and overlap–save methods), * fast algorithms for
discrete cosine Discrete may refer to: *Discrete particle or quantum in physics, for example in quantum theory * Discrete device, an electronic component with just one circuit element, either passive or active, other than an integrated circuit * Discrete group, a ...
or sine transforms (e.g. fast DCT used for
JPEG JPEG ( ) is a commonly used method of lossy compression for digital images, particularly for those images produced by digital photography. The degree of compression can be adjusted, allowing a selectable tradeoff between storage size and imag ...
and
MPEG The Moving Picture Experts Group (MPEG) is an alliance of working groups established jointly by ISO and IEC that sets standards for media coding, including compression coding of audio, video, graphics, and genomic data; and transmission and f ...
/
MP3 MP3 (formally MPEG-1 Audio Layer III or MPEG-2 Audio Layer III) is a coding format for digital audio developed largely by the Fraunhofer Society in Germany, with support from other digital scientists in the United States and elsewhere. Origin ...
encoding and decoding), * fast Chebyshev approximation, * solving
difference equation In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
s, * computation of isotopic distributions. * modulation and demodulation of complex data symbols using orthogonal frequency division multiplexing (OFDM) for 5G, LTE, Wi-Fi, DSL, and other modern communication systems.


Research areas

; Big FFTs: With the explosion of big data in fields such as astronomy, the need for 512K FFTs has arisen for certain interferometry calculations. The data collected by projects such as WMAP and
LIGO The Laser Interferometer Gravitational-Wave Observatory (LIGO) is a large-scale physics experiment and observatory designed to detect cosmic gravitational waves and to develop gravitational-wave observations as an astronomical tool. Two large ...
require FFTs of tens of billions of points. As this size does not fit into main memory, so called out-of-core FFTs are an active area of research. ; Approximate FFTs: For applications such as MRI, it is necessary to compute DFTs for nonuniformly spaced grid points and/or frequencies. Multipole based approaches can compute approximate quantities with factor of runtime increase. ; Group FFTs: The FFT may also be explained and interpreted using
group representation theory In the mathematical field of representation theory, group representations describe abstract groups in terms of bijective linear transformations of a vector space to itself (i.e. vector space automorphisms); in particular, they can be used to re ...
allowing for further generalization. A function on any compact group, including non-cyclic, has an expansion in terms of a basis of irreducible matrix elements. It remains active area of research to find efficient algorithm for performing this change of basis. Applications including efficient
spherical harmonic In mathematics and physical science, spherical harmonics are special functions defined on the surface of a sphere. They are often employed in solving partial differential equations in many scientific fields. Since the spherical harmonics form ...
expansion, analyzing certain
Markov process A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happen ...
es, robotics etc. ; Quantum FFTs: Shor's fast algorithm for
integer factorization In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization. When the numbers are s ...
on a quantum computer has a subroutine to compute DFT of a binary vector. This is implemented as sequence of 1- or 2-bit quantum gates now known as quantum FFT, which is effectively the Cooley–Tukey FFT realized as a particular factorization of the Fourier matrix. Extension to these ideas is currently being explored.


Language reference


See also

FFT-related algorithms: * Goertzel algorithm – computes individual terms of discrete Fourier transform FFT implementations: *
ALGLIB ALGLIB is a cross-platform open source numerical analysis and data processing library. It can be used from several programming languages (C++, C#, VB.NET, Python, Delphi). ALGLIB started in 1999 and has a long history of steady development wi ...
– a dual/GPL-licensed C++ and C# library (also supporting other languages), with real/complex FFT implementation *
FFTPACK FFTPACK is a package of Fortran subroutines for the fast Fourier transform. It includes complex, real Real may refer to: Currencies * Brazilian real (R$) * Central American Republic real * Mexican real * Portuguese real * Spanish real * Sp ...
– another Fortran FFT library (public domain) * Architecture-specific: ** Arm Performance Libraries ** Intel Integrated Performance Primitives ** Intel
Math Kernel Library Intel oneAPI Math Kernel Library (Intel oneMKL; formerly Intel Math Kernel Library or Intel MKL) is a library of optimized math routines for science, engineering, and financial applications. Core math functions include BLAS, LAPACK, ScaLAPAC ...
* Many more implementations are available, for CPUs and GPUs, such as PocketFFT for C++ Other links: * Odlyzko–Schönhage algorithm applies the FFT to finite
Dirichlet series In mathematics, a Dirichlet series is any series of the form \sum_^\infty \frac, where ''s'' is complex, and a_n is a complex sequence. It is a special case of general Dirichlet series. Dirichlet series play a variety of important roles in analy ...
*
Schönhage–Strassen algorithm The Schönhage–Strassen algorithm is an asymptotically fast multiplication algorithm for large integers. It was developed by Arnold Schönhage and Volker Strassen in 1971.A. Schönhage and V. Strassen,Schnelle Multiplikation großer Zahlen, ...
– asymptotically fast multiplication algorithm for large integers *
Butterfly diagram In the context of fast Fourier transform algorithms, a butterfly is a portion of the computation that combines the results of smaller discrete Fourier transforms (DFTs) into a larger DFT, or vice versa (breaking a larger DFT up into subtransforms ...
– a diagram used to describe FFTs *
Spectral music Spectral music uses the acoustic properties of sound – or sound spectra – as a basis for composition. Definition Defined in technical language, spectral music is an acoustic musical practice where compositional decisions are often informe ...
(involves application of DFT analysis to musical composition) *
Spectrum analyzer A spectrum analyzer measures the magnitude of an input signal versus frequency within the full frequency range of the instrument. The primary use is to measure the power of the spectrum of known and unknown signals. The input signal that most co ...
– any of several devices that perform spectrum analysis, often via a DFT *
Time series In mathematics, a time series is a series of data points indexed (or listed or graphed) in time order. Most commonly, a time series is a sequence taken at successive equally spaced points in time. Thus it is a sequence of discrete-time data. Ex ...
*
Fast Walsh–Hadamard transform In computational mathematics, the Hadamard ordered fast Walsh–Hadamard transform (FWHT''h'') is an efficient algorithm to compute the Walsh–Hadamard transform (WHT). A naive implementation of the WHT of order n = 2^m would have a Computation ...
*
Generalized distributive law The generalized distributive law (GDL) is a generalization of the distributive property which gives rise to a general message passing algorithm. It is a synthesis of the work of many authors in the information theory, digital communications, sign ...
*
Least-squares spectral analysis Least-squares spectral analysis (LSSA) is a method of estimating a frequency spectrum, based on a least squares fit of sinusoids to data samples, similar to Fourier analysis. Fourier analysis, the most used spectral method in science, generally ...
* Multidimensional transform * Multidimensional discrete convolution * Fast Fourier Transform Telescope


References


Further reading

* * * * * * * (NB. Contains extensive bibliography.) * Elena Prestini: "The Evolution of Applied Harmonic Analysis", Springer, ISBN 978-0-8176-4125-2 (2004), Sec.3.10 'Gauss and the asteroids: history of the FFT'.


External links


Fast Fourier Transform for Polynomial Multiplication
fast Fourier algorithm *
Fast Fourier Transforms
', Connexions online book edited by Charles Sidney Burrus, with chapters by Charles Sidney Burrus, Ivan Selesnick, Markus Pueschel, Matteo Frigo, and Steven G. Johnson (2008)
Fast Fourier transform — FFT
FFT programming in C++ the Cooley–Tukey algorithm
Online documentation, links, book, and code
* Sri Welaratna,
Thirty years of FFT analyzers
", ''Sound and Vibration'' (January 1997, 30th anniversary issue) a historical review of hardware FFT devices
ALGLIB FFT Code
a dual/GPL-licensed multilanguage (VBA, C++, Pascal, etc.) numerical analysis and data processing library
SFFT: Sparse Fast Fourier Transform
MIT's sparse (sub-linear time) FFT algorithm, sFFT, and implementation
VB6 FFT
a VB6 optimized library implementation with source code

a visual interactive intro to Fourier transforms and FFT methods {{Authority control FFT algorithms Digital signal processing Discrete transforms