The FFT through polynomial multiplication

Source: The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever?, Reducible, 28:23, uploaded 2020-11-14.

The video discovers the FFT through polynomial multiplication. Four ideas arrive in sequence: change representation, reuse work across positive–negative point pairs, choose roots of unity so the reuse survives recursion, and recognise that interpolation is almost the same transform in reverse.

Why polynomial multiplication is the teaching problem

Multiplying coefficients directly makes every term of one polynomial interact with every term of the other. Two degree-$d$ inputs produce degree $2d$, and the straightforward coefficient convolution takes quadratic work.

The operation itself is not inherently difficult in every representation. If both polynomials are known at the same $n$ points, multiplying them requires only $n$ independent scalar products. The difficult step moves to converting between representations.

Two polynomial representations

A degree-$d$ polynomial can be represented by its coefficients or by its values at $d+1$ distinct points.

• In coefficient form, multiplying two polynomials requires every coefficient of one to interact with every coefficient of the other.
• In value form, multiplication is pointwise. Evaluate both polynomials at the same points, multiply corresponding values, then interpolate the resulting polynomial.

The complete multiplication pipeline is therefore:

1. Pad both coefficient lists so the result degree fits.
2. Evaluate both polynomials at the same sufficiently large set of points.
3. Multiply corresponding values.
4. Interpolate the result back into coefficients.

Naive evaluation and interpolation are still quadratic, so nothing has been won yet. The FFT is the fast conversion.

First attempt: positive and negative pairs

Separate a polynomial into even and odd coefficients:

Evaluating at $x$ and $-x$ reuses the same two results:

Both smaller polynomials depend on $x^2$. If the requested points arrive as positive–negative pairs, the algorithm only has to evaluate at half as many squared points and can reconstruct both signs. The original size-$n$ problem becomes two size-$n/2$ evaluations plus linear combination work, suggesting $O(n\log n)$.

The first attempt breaks at the next recursive level. Squaring ordinary positive and negative real points produces only positive values, so the new point set no longer contains pairs.

Roots of unity make the recursion close

The repair requires complex points. For a four-point evaluation, choose $1,-1,\mathrm{i},-\mathrm{i}$, the four solutions of $x^4=1$. They form positive–negative pairs; after squaring, they become $1,-1,1,-1$, exactly the two roots required by the half-size subproblems.

For general $n$, choose the $n$th roots of unity, equally spaced around the unit circle:

They have the two properties the recursion needs:

• $\omega_n^{j+n/2}=-\omega_n^j$, so the points form positive–negative pairs.
• Squaring the $n$ roots produces the $n/2$ roots of unity, so the same structure appears at every level.

The input coefficient length is padded to a power of two in the video’s radix-2 version. Splitting even and odd coefficients, recursively evaluating both at the smaller root set, and combining them with powers of $\omega_n$ yields all values. Two half-size calls and $O(n)$ combination work across $\log_2 n$ levels give $O(n\log n)$.

The video then translates the recurrence into eleven lines of code. The brevity is the consequence of the mathematical point choice, not a separate optimisation trick.

Why this is the DFT

Polynomial evaluation at the roots of unity can be written as a matrix–vector product. The matrix entries are powers of $\omega_n$, which is precisely the DFT matrix under the video’s sign convention. The FFT is therefore an efficient algorithm for multiplying that structured matrix by a vector.

Polynomial multiplication is one place the matrix appears. Spectral analysis and convolution use the same transform for different semantic reasons.

Inverse FFT

Interpolation initially appears harder: recover coefficients from values. In matrix form it means multiplying by the inverse DFT matrix. That inverse has almost the same structure as the forward matrix: replace $\omega_n$ with $\omega_n^{-1}$ and apply an overall $1/n$ normalisation.

The same recursive code can consequently run with the exponent’s sign reversed, followed by division by $n$. The implementation shown in the transcript folds the normalisation into its root choice, while the note follows the conventional and less error-prone statement: apply $1/n$ once to the complete inverse result. The video’s description explicitly corrects an earlier normalisation error.

The four ideas in the final pipeline

1. Point-value representation turns multiplication into a linear pointwise operation.
2. Even–odd splitting reuses evaluation across $x$ and $-x$.
3. Roots of unity preserve those pairs under repeated squaring.
4. The inverse DFT reuses the forward structure for interpolation.

After two FFT evaluations, $n$ pointwise multiplications, and one inverse FFT, polynomial multiplication falls from quadratic to $O(n\log n)$ for the padded problem.

Takeaways

• The FFT is an algorithm for the DFT, not a different transform.
• Its speedup comes from representation, symmetry, recursion, and reuse.
• Polynomial multiplication is the teaching case; the same algorithm powers convolution, spectral analysis, communications, image processing, and numerical methods.
• Radix-2 recursion is clearest for powers of two, but other FFT factorizations exist.

Further reading / references

• Cormen et al., Introduction to Algorithms.
• Papadimitriou et al., Algorithms.
• Reducible’s animation source.