Chapter 30 — Polynomials and the FFT

This is the canonical CLRS fourth-edition chapter guide during the migration period.

Current source

Sections 30.1--30.3 are native fourth-edition sections (representing polynomials, the DFT and FFT, and efficient FFT implementations), imported directly from Section 30.1, Section 30.2, and Section 30.3. Declarations keep their current namespaces; the third-edition-numbered imports CLRSLean.Chapter_30 and CLRSLean.Chapter_30.Section_30_* forward to these sources.

Implementation details

The supporting implementation pages remain available outside the main sidebar:

• Fixed-Capacity Coefficient Vectors

• Point-Value Interpolation

• Representation Operations

• Roots of Unity

• The Generic DFT

• Inversion and Convolution

• Recursive Radix-2 FFT

• FFT Polynomial Multiplication

• Bit-Reversal Permutation

• Iterative Radix-2 FFT

• Parallel Network Size and Depth

Coverage boundary

The native sections supply the represented fourth-edition polynomial/FFT sections (the FFT correctness and work analysis, the bit-reversal and iterative-FFT implementations, and the parallel FFT).

See docs/clrs-fourth-edition-map.csv for the section-level mapping and docs/migrations/clrs4.md for compatibility and deprecation policy.