Numerical Methods

Fast Fourier Transform

Цели урока

  • Understand the Cooley-Tukey algorithm: how recursive splitting of DFT into even/odd reduces complexity from O(N^2) to O(N log N)
  • Learn to apply FFT convolution for polynomial multiplication and PDE solving with constant coefficients
  • Understand NTT, FFTW, and spectral differentiation as key applications of FFT

Предварительные знания

  • Multigrid Methods
  • Multigrid Methods

Multiplying two degree-10^6 polynomials naively takes 10^12 operations - more than a second even on modern CPUs. FFT does it in 20 million operations.

  • Shazam and Spotify: audio fingerprinting in milliseconds via FFT spectrograms
  • RSA and post-quantum crypto Kyber: multiplying large numbers and polynomials via NTT
  • NOAA global atmospheric models: pseudospectral methods via FFT
  • PyTorch torch.nn.Conv2d: large convolutions computed via cuFFT on GPU

History of the Algorithm

Cooley and Tukey in 1965 rediscovered the algorithm - it turned out Gauss knew about it in 1805 but never published. Their Mathematics of Computation paper transformed signal processing. Harvard's Rader (1968) generalized to arbitrary N. Today FFTW (Frigo, Johnson, MIT, 1997) is the de-facto standard, used in NumPy, MATLAB, GNU Radio.

Cooley-Tukey Algorithm: Divide-and-Conquer Fourier

1965. Cooley and Tukey published an algorithm that IEEE called one of the 10 most important algorithms of the 20th century. DFT complexity dropped from O(N^2) to O(N log N). For N = 1,000,000: 10^12 operations versus 20 million. A factor of 50,000.

0

1

Sign In

Spotify uses FFT for audio fingerprinting: a 30-second fragment at 44,100 Hz is processed in 2 milliseconds instead of 4 seconds. Every Shazam match is FFT in real time. Every convolution in PyTorch is FFT under the hood.

For arbitrary N, mixed-radix FFT or Bluestein's chirp-z algorithm handles any size. numpy.fft.fft accepts any N and internally selects the optimal algorithm via pocketfft.

Why does Radix-2 FFT require N = 2^m?

Radix-2 recursively divides: DFT(N) -> DFT(N/2) + DFT(N/2). Requires N = 2^m to divide down to N=1. For arbitrary N, use mixed-radix FFT.

FFT for PDE Solving and Polynomial Multiplication

FFT is not just about sound. Multiplying two degree-N polynomials takes O(N^2) naively and O(N log N) via FFT. Java and Python BigInteger libraries use this. RSA with 4096-bit keys relies on multiplying enormous numbers - FFT convolution.

Pseudospectral method for PDEs: the derivative of a function equals multiplication by ik in Fourier space. The Poisson equation becomes division by -k^2. One FFT forward, one operation, one FFT back. For periodic problems, this is more accurate than FEM with the same number of nodes.

Gibbs phenomenon: FFT methods produce oscillations near discontinuities (apply Hann windowing or Cesaro summation). For non-smooth problems, finite differences or adaptive FEM may be preferable.

Why is FFT polynomial multiplication faster than the naive O(N^2) approach?

Strategy: coefficients -> values (FFT, O(N log N)) -> elementwise multiply (O(N)) -> values -> coefficients (IFFT, O(N log N)). Total O(N log N) vs O(N^2).

NTT, FFTW, and Spectral Differentiation

FFTW (Fastest Fourier Transform in the West, MIT) is used in MATLAB, NumPy, scipy. It auto-selects the optimal algorithm for a given N and architecture (SIMD, cache, multi-core). In practice 2-5x faster than a naive implementation.

In PyTorch and TensorFlow, convolution is implemented via FFT for sufficiently large kernels. torch.fft.fft2 uses cuFFT on GPU. FlashAttention-2 uses tiling strategies analogous to FFTW optimizations for the attention computation.

How does NTT (Number Theoretic Transform) fundamentally differ from FFT?

NTT replaces exp(-2pi*i/N) with a primitive N-th root of unity in Z_p. All operations are integer modular arithmetic. The result is exact, with no floating-point error accumulation.

Connections to Other Topics

FFT is the foundation of spectral methods (nm-23), used in multigrid for spectral smoothers (nm-21). Pseudospectral PDE solvers apply FFT for differentiation. In ML: convolutions in CNNs, computing attention via FFT for long sequences.

  • Related Topics — Related topic

Итоги

  • FFT reduces DFT complexity from O(N^2) to O(N log N) via recursive even/odd splitting: butterfly combines two N/2-DFTs in N operations
  • FFT convolution: coefficients -> values (FFT) -> elementwise multiply -> coefficients (IFFT); polynomial multiplication in O(N log N)
  • Spectral derivative = multiply Fourier coefficients by ik; machine precision for smooth periodic functions
  • NTT: FFT in finite fields Z_p for exact integer arithmetic; FFTW auto-selects the optimal algorithm per architecture

Вопросы для размышления

  • Gauss knew the FFT algorithm in 1805 but it wasn't applied until 1965. What changed that made it suddenly practical?
  • Spectral differentiation gives machine precision for smooth functions but oscillates near discontinuities (Gibbs). How does this affect the choice of method for problems with shock waves?
  • PyTorch uses FFT for large convolutions. At what kernel size does the FFT approach become faster than direct convolution, and why?

Связанные уроки

  • nm-21 — multigrid uses FFT in spectral smoothers
  • nm-23 — spectral methods are built on FFT
  • nm-25-autodiff — FFT convolutions use autodiff in PyTorch
  • la-01-vectors-intro
Fast Fourier Transform