Astrophysics (index)

Fast Fourier Transform

(efficient algorithm for calculating a discrete Fourier transform)

Fast Fourier Transform (FFT) can refer to any of a number of algorithms that calculate a Discrete Fourier Transform (DST) more efficiently than the obvious 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, reducing weeks of required CPU to seconds or 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 DST results for selections of the input data to produce the answer, carrying out the full calculation recursively.

The inverse of the DST (Inverse Discrete Fourier Transform, IDST), 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 DST: phase information is lost.) In fact, the bulk of the IDST work is identical to the DST, and the word "inverse" is often skipped. 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.


Referenced by:
Fast Fourier Transform Telescope
Imaging Fourier Transform Spectroscopy (IFTS)