Fast Fourier transform

Remarks

For $N = 2^m$ the radix-2 Cooley–Tukey algorithm gives the bound: it uses $\frac{N}{2} \log_2 N$ complex multiplications and $N \log_2 N$ complex additions. For general $N$, Bluestein's algorithm rewrites the transform as a cyclic convolution of a power-of-two length $M < 4N$, computed by three radix-2 FFTs plus $O(N)$ operations. Evaluating the $N$ defining sums directly needs about $N^2$ multiplications, so the gain is a factor of order $N / \log N$. The inverse transform has the same form with $e^{+2\pi i nk/N}$ and a factor $1/N$, so it is also computed by an FFT. The bound counts arithmetic operations. In floating-point arithmetic the FFT is also accurate: its normwise error bound grows like $\log_2 N$ times the unit roundoff, against about $N$ times for direct evaluation. Whether $\Theta(N \log N)$ operations are necessary is not known in general; lower bounds are known only for restricted models of computation.

Going deeper

For a student

"FFT" names a family of algorithms rather than one method: Cooley–Tukey for composite lengths, the prime-factor algorithm for coprime factors, and Rader's or Bluestein's algorithm for prime lengths. All exploit the structure of the DFT matrix $(\omega^{nk})$, which factors into $O(\log N)$ sparse matrices. Combined with the cyclic convolution property of the DFT, the FFT computes convolutions and polynomial products of length $N$ in $O(N \log N)$ operations. Spectral methods for differential equations and fast polynomial interpolation at roots of unity rest on this.