Opening Multiplication via the Discrete Fourier Transform
Multiplication via the Discrete Fourier Transform
- Length
- 26 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 4: Polynomial multiplication as integer multiplication
Fast multiplication of integers relies on framing the operation as the multiplication of polynomials whose coefficients are the digits. Carnegie Mellon professor Ryan O'Donnell shows how evaluating these polynomials at complex roots of unity allows the computation to pass through a value representation. Evaluating a polynomial at distinct points naively takes quadratic time, but choosing roots of unity introduces algebraic symmetry that enables fast evaluation and interpolation. Using the Discrete Fourier Transform matrix and the Fast Fourier Transform algorithm, the multiplication reduces from steps to operations. The lecture concludes by setting up the foundations for the FFT algorithm using complex roots of unity.

Your comment is kept while you sign up.Sign in
O'Donnell recasts integer multiplication as polynomial multiplication routed through values at complex roots of unity.
Fast multiplication of integers relies on framing the operation as the multiplication of polynomials whose coefficients are the digits. Carnegie Mellon professor Ryan O'Donnell shows how evaluating these polynomials at complex roots of unity allows the computation to pass through a value representation. Evaluating a polynomial at distinct points naively takes quadratic time, but choosing roots of unity introduces algebraic symmetry that enables fast evaluation and interpolation. Using the Discrete Fourier Transform matrix and the Fast Fourier Transform algorithm, the multiplication reduces from steps to operations. The lecture concludes by setting up the foundations for the FFT algorithm using complex roots of unity.
Modern Computer Arithmetic
The Art of Computer Programming, Vol. 2
Integer multiplication in time O(n log n)
This lecture
Lecture 19 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.