| Astrophysics (Index) | About |
The term, fast Fourier transform (FFT) can refer to any of a number of algorithms that calculate a discrete Fourier transform (DFT) more efficiently than the straightforward method. This is accomplished by arranging the calculations so as to reduce repetition of those that are identical. Its use reduces the complexity of the calculation from O(N²) to O(N log N), making DFTs practical for more applications, in some cases reducing weeks of required computation to seconds or even millennia to weeks.
The discrete Fourier transform effectively applies the Fourier transform to a finite set of sample results of a function, from an evenly-spaced set of sample values over an interval. Assuming the function over that interval is a single repetition of a periodic function, it calculates the magnitude of each harmonic, in effect, the magnitude of the sine waves that could be individually phased so that summing them would approximate the original function. The DFT's defining formula is:
N-1
Xk = Σ xne-i2πkn/N
n=0
For N input values, xk, producing N output values, Xn.
A commonly-used FFT algorithm splits the input data into two sets of data, calculates the DFT of each, and then carries out a procedure that produces the DFT of all the data from this pair of results. It does this recursively, i.e., uses the same FFT algorithm for each half, until each set of data is trivially small.
The inverse of the DFT (inverse discrete Fourier transform, IDFT), creating samples of a function that has a specific set of harmonics, is also useful. (Applying the inverse does not entirely "undo" the application of the DFT: phase information is lost.) In fact, the bulk of the IDFT calculation is identical to that of the DFT, and in referring to it, the word "inverse" is often skipped, i.e., when someone says DFT, they may be referring to the IDFT. The efficient FFT algorithms also apply, and the terms "FFT" and "fast Fourier transform" (with no "I" or "inverse" mentioned) are typically used for this process as well.