Franz Franchetti and Markus Püschel (in Encyclopedia of Parallel Computing, Eds. David Padua, Springer 2011)
Fast Fourier Transform
Comment: The abstract below is the definition used in the encyclopedia
Preprint (874 KB)
Published paper (link to publisher)

A fast Fourier transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) of an input vector. Efficient means that the FFT computes the DFT of an n-element vector in O(n log n) operations in contrast to the O(n^2) operations required for computing the DFT by definition. FFTs exist for any vector length $n$ and for real and higher-dimensional data. Parallel FFTs have been developed since the advent of parallel computing.

SIMD vectorization, Discrete/fast Fourier transform, Parallel processing