Chapter 30: Polynomials and the FFT: DFT, FFT, and Circuit Representation

A polynomial in coefficient form supports fast addition and evaluation via Horner's rule but requires Θ(n²) time for naive multiplication, while point-value form makes multiplication trivially pointwise — motivating a strategy of converting to point-values, multiplying, and converting back. The key insight is to evaluate both polynomials at the n-th roots of unity — the n complex numbers e^(2πik/n) satisfying ωⁿ = 1 — whose algebraic properties, captured in the cancellation, halving, and summation lemmas, enable recursive evaluation by splitting a polynomial A(x) into its even- and odd-indexed coefficient polynomials A_even(x²) and A_odd(x²), recursively evaluating each at the squares of the roots, and combining results using twiddle factors ωₙᵏ — all requiring input size to be a power of 2. The Discrete Fourier Transform (DFT) formalizes this evaluation as a matrix-vector product taking Θ(n²) naively, which the FFT reduces to Θ(n log n) through this recursive structure, with the inverse FFT symmetric in form — swapping ωₙ with ωₙ⁻¹ and dividing by n — to recover coefficients from point values. The convolution theorem unifies the approach: the product polynomial's coefficient vector equals the inverse DFT of the componentwise product of the two inputs' DFTs, expressed as c = DFT⁻¹(DFT(a) ⊙ DFT(b)), with inputs padded to length 2n to prevent wrap-around artifacts. Physically, the FFT maps to a circuit of log n stages with n/2 butterfly operations per stage — each combining two values with a twiddle factor — achieving depth Θ(log n) and total work Θ(n log n), making it ubiquitous in digital signal processing, image analysis, and hardware acceleration.