Polynomials & the Fast Fourier Transform (FFT) Explained | Chapter 30 in Introduction to Algorithms

Chapter 30 of Introduction to Algorithms explores the Fast Fourier Transform (FFT), a groundbreaking algorithm for multiplying polynomials efficiently in Θ(n log n) time. The chapter walks through the transition between coefficient and point-value forms of a polynomial, explains the mathematical role of complex roots of unity, and introduces the convolution theorem that underlies many applications in digital signal processing, image analysis, and algorithm design.

Watch the video above for a guided walkthrough of FFT and its applications in algorithmic polynomial operations, and don’t forget to subscribe to Last Minute Lecture for more expert chapter summaries from core textbooks.

Polynomial Representations: Coefficient vs Point-Value Form

A polynomial can be represented in two forms:

• Coefficient form: A(x) = a₀ + a₁x + ... + aₙ₋₁xⁿ⁻¹ — efficient for evaluation via Horner’s Rule, but naive multiplication is Θ(n²).
• Point-value form: A set of pairs (xₖ, A(xₖ)) — enables fast multiplication if both polynomials are evaluated at the same points.

The FFT allows fast conversion between these forms using complex roots of unity, enabling a highly efficient method to multiply large-degree polynomials.

Fast Multiplication Using FFT

Here’s how FFT accelerates polynomial multiplication:

1. Pad polynomials to degree 2n and evaluate at 2n points.
2. Multiply values pointwise: C(xₖ) = A(xₖ) × B(xₖ).
3. Interpolate using inverse FFT to retrieve coefficients of C(x).

This process lowers the time complexity from Θ(n²) to Θ(n log n), offering dramatic improvements for large input sizes.

Complex Roots of Unity and Recursive Evaluation

A complex number ω is called an n-th root of unity if ωⁿ = 1. Chapter 30 introduces:

• Principal root of unity: ωₙ = e^(2πi/n)
• Recursive properties like the cancellation lemma, halving lemma, and summation lemma that support FFT’s divide-and-conquer design.

These roots allow for efficient evaluation and interpolation of polynomials at specific complex points used in the Discrete Fourier Transform.

From DFT to FFT: Speeding Up the Transform

The Discrete Fourier Transform (DFT) converts a coefficient vector into a vector of point-values via matrix-vector multiplication, typically in Θ(n²) time. The FFT reduces this to Θ(n log n) using recursive decomposition:

• Splits A(x) into even and odd sub-polynomials: A_even(x²) and x × A_odd(x²).
• Combines results using twiddle factors: ωₙ^k.
• Works best when input size is a power of 2.

The inverse FFT is nearly identical — just swap ωₙ with ωₙ⁻¹ and divide the final result by n.

Convolution Theorem & Polynomial Multiplication

Chapter 30 proves that convolution of two sequences (vectors of coefficients) is equivalent to polynomial multiplication:

c = DFT⁻¹(DFT(a) ⊙ DFT(b)), where ⊙ denotes pointwise multiplication.

This is the backbone of FFT-based multiplication, especially in applications like digital filtering, signal transformation, and efficient numerical computation.

FFT Circuits and Parallelism

The structure of FFT lends itself to recursive hardware design:

• Butterfly operation: Core element combining pairs of inputs using twiddle factors.
• Bit-reversal permutation: Reorders inputs/outputs based on binary index reversal.
• Performance: log n stages with n/2 operations each → total Θ(n log n) time.

This makes FFT circuits ideal for hardware implementations in DSP chips and GPU acceleration.

Conclusion

Chapter 30 reveals how the Fast Fourier Transform transforms polynomial multiplication from a quadratic-time problem into a logarithmic-time powerhouse. By mastering roots of unity, the structure of the DFT, and the application of convolution, students gain a deep understanding of one of the most influential algorithms in applied computer science and engineering.

🎥 Prefer a video breakdown? Watch the full podcast-style summary above and check out more videos on the Last Minute Lecture channel.

If you found this breakdown helpful, be sure to subscribe to Last Minute Lecture for more chapter-by-chapter textbook summaries and academic study guides.