FFTs

FFTs, or fast Fourier transforms, are a family of algorithms for computing the discrete Fourier transform (DFT) and its inverse efficiently. The DFT transforms a sequence of complex numbers into its frequency-domain representation. The straightforward DFT requires O(N^2) operations; FFTs reduce this to O(N log N), making practical analysis and processing of signals feasible for large N.

Most FFTs are divide-and-conquer algorithms. The canonical Cooley–Tukey FFT splits an N-point DFT into two N/2-point DFTs by separating even- and odd-indexed samples, recursively. The radix-2 version is popular when N is a power of two; general-purpose FFTs use mixed-radix and other techniques to handle arbitrary N, including Bluestein’s algorithm and Rader’s algorithm.

Implementation notes: many FFTs are in-place and require a bit-reversal permutation of outputs. Real-input FFTs exploit symmetry to halve work. Numerical accuracy depends on data type and scaling conventions; results are subject to floating-point errors.

Applications: spectral analysis, digital filtering, convolution via the convolution theorem, and efficient multiplication of polynomials or large integers. Two-dimensional FFTs are used in image and video processing. FFT libraries provide highly optimized routines across architectures and platforms, enabling fast frequency-domain processing in many data-intensive applications.