Astrophysics (Index)About

fast Fourier transform

(efficient algorithm for calculating a discrete Fourier transform)

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 straight-forward method. This is accomplished by arranging the calculations and using equivalences so some of the early calculations can be reused. Its use reduces the complexity of the calculation from O(N²) to O(N log N), making many more potential uses practical, sometimes 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. Its defining formula is:

Xk = Σ xne-i2πkn/N

For N input values, xk, producing N output values, Xn.

A commonly-used FFT algorithm uses a method of combining DFT results for selections of the input data to produce the DFT for the combinations of these selections, carrying out the full calculation by doing this recursively.

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.

Further reading:

Referenced by pages:
fast folding algorithm (FFA)
Fast Fourier Transform Telescope
Fourier transform (FT)
imaging Fourier transform spectroscopy (IFTS)
numerical analysis
spectral correlator
spectral density