Lecture 3: Divide & Conquer: FFT

What this lecture covers

This lecture, taught by Professor Erik Demaine, tackles polynomial multiplication: the naive algorithm takes quadratic time, and the goal is to bring it down to n log n. Along the way it develops the fast Fourier transform (FFT), one of the most widely used algorithms in computing, as a divide-and-conquer technique built on complex roots of unity.

By the end, you can compare coefficient, root, and sample representations of a polynomial and explain their trade-offs for evaluation, addition, and multiplication; explain why splitting a polynomial into even- and odd-indexed coefficients, evaluated at the roots of unity, makes the divide-and-conquer recursion collapse in size at each level; and describe how the same algorithm, with a sign flip, computes the inverse transform needed to convert results back to coefficient form.

Key ideas

• Three polynomial operations: evaluation, addition, and multiplication, each easy in some representations and hard in others.
• Coefficient representation: evaluation and addition are linear time; multiplication is Theta(n^2) because each output coefficient is a sum over pairs of input coefficients.
• Root representation: multiplication is trivial (concatenate root lists), but addition is effectively infeasible, and computing roots from coefficients has no general closed-form solution for degree five and above.
• Sample representation: given a polynomial's values at a fixed set of points, addition and multiplication of two polynomials become pointwise operations on the samples, both linear time; the catch is converting between coefficients and samples.
• Vandermonde matrix: evaluating a polynomial at n points is a matrix-vector product V*a that costs Theta(n^2) in general, and the reverse (interpolation) costs the same using the matrix inverse.
• Divide by parity: splitting a polynomial's coefficients into even-indexed and odd-indexed halves, rather than into a left and right half, lets A(x) be reconstructed from A_even(x^2) and A_odd(x^2) with one multiplication and one addition.
• Collapsing sets and roots of unity: choosing the evaluation points to be the n-th roots of unity on the complex unit circle makes the set of squared points shrink by half at every recursion level, turning the recurrence into the familiar T(n) = 2T(n/2) + Theta(n), which solves to Theta(n log n).
• Fast polynomial multiplication: transform both polynomials to samples via FFT (Theta(n log n)), multiply samples pointwise (Theta(n)), then apply the inverse FFT to get the coefficients of the product.
• Inverse FFT: replacing each root of unity with its complex conjugate (equivalently, flipping the sign in the exponent) and dividing by n runs the same algorithm backwards, proved using the fact that V times its complex conjugate equals n times the identity matrix.

Walkthrough

Polynomial operations and their costs (0:00)

Demaine defines a polynomial by its coefficient vector and reviews evaluation, using Horner's rule for Theta(n) time; addition, which is Theta(n) by summing corresponding coefficients; and multiplication, whose direct formula c_k = sum(a_j * b_(k-j)) costs Theta(n^2). He also connects polynomial multiplication to convolution, used throughout signal and image processing, motivating why a faster multiplication algorithm matters.

Comparing representations (13:23)

The class discusses three representations: coefficient vectors, roots, and samples (values of the polynomial at fixed points). A table of the three operations against the three representations shows each representation is good at some operations and bad at others: coefficients are good for addition but bad for multiplication; roots are good for multiplication but addition is essentially unworkable; samples are good for both addition and multiplication but evaluating at an arbitrary new point (interpolation) is expensive. The lecture settles on converting between coefficients and samples as the strategy, since multiplication is easy in sample form.

Why naive conversion is too slow (22:29)

Converting from coefficients to samples is a Vandermonde matrix-vector product, Theta(n^2); converting back (interpolation) via computing the matrix inverse is also Theta(n^2), or Theta(n^3) once per new set of points. Since the goal is to beat quadratic time overall, this naive conversion isn't good enough, motivating a smarter algorithm.

Dividing by parity (30:43)

Instead of splitting a polynomial's coefficients into a left half and right half, Demaine splits them by parity into A_even and A_odd, each with half as many terms. Algebraically, A(x) = A_even(x^2) + x * A_odd(x^2), so evaluating A at a set of points X reduces to evaluating A_even and A_odd at the set X^2 (each point squared). This gives a recurrence T(n, |X|) = 2*T(n/2, |X|) + Theta(n + |X|), which is still Theta(n^2) unless the evaluation set itself shrinks at each level.

Roots of unity make the recursion collapse (43:04)

The key insight is choosing the evaluation points so that squaring them halves the set size. Demaine shows that the n-th roots of unity, n equally spaced points on the complex unit circle, have exactly this "collapsing" property: squaring a root of unity doubles its angle on the circle, so the n-th roots of unity square down to the n/2-th roots of unity, and so on recursively down to a single point. This requires working with complex numbers and uses Euler's formula (e^(i*theta) = cos(theta) + i*sin(theta)) to relate the roots geometrically. With this choice, the recurrence becomes the familiar T(n) = 2T(n/2) + Theta(n), giving Theta(n log n), which is the fast Fourier transform.

Fast polynomial multiplication and the inverse transform (1:03:28)

Putting it together: run FFT on both polynomials to get their samples at the n-th roots of unity, multiply the samples pointwise in linear time, then invert the transform to recover the coefficients of the product. Demaine shows that the inverse transform uses the same algorithm, just replacing each root of unity with its complex conjugate and dividing the result by n; he proves this by showing V times its complex conjugate transpose equals n times the identity matrix, using a geometric series argument on the roots of unity.

Applications (1:17:46)

The lecture closes with a brief tour of FFT applications: converting an audio signal between the time domain and frequency domain to apply high-pass or low-pass filters, image blurring, and its role in software like FFTW (developed at MIT) and hardware such as noise-canceling headsets and MP3 compression.

Before you watch

• Review the divide-and-conquer recurrence pattern and recursion tree analysis from Lecture 2, since this lecture reuses that framework with a twist (a non-shrinking parameter that must be made to shrink).
• Basic familiarity with complex numbers (the complex plane, magnitude, and Euler's formula) helps, though the lecture builds up the geometric intuition from scratch.

Check your understanding

1. For each of coefficient, root, and sample representations, which of evaluation, addition, and multiplication is hard, and why?
2. Why does splitting a polynomial's coefficients into even- and odd-indexed halves, rather than a left and right half, make it possible to reduce evaluation at a set X to evaluation at the set X^2?
3. What property of the n-th roots of unity makes the set of evaluation points shrink by half at each level of the recursion?
4. Why must the evaluation points be complex numbers rather than real numbers for this algorithm to work?
5. How does the inverse FFT reuse the same algorithm as the forward FFT, and what two changes are needed to compute it?