Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 30

The author discusses fast fourier transform (FFT). The author defines a polynomial of variable $x$ over a field $F$. The author defines coefficients of the polynomial and degree of a polynomial. The author defines two operations; polynomial addition and multiplication.

The author describes two ways to present polynomials:

• Co-efficient representation
• Point-value representation

The author proves uniqueness of an interpolating polynomial theorem and and provides a method for fast multiplication of polynomial in co-efficient form.

The author then defines complex roots of unity, study their properties, define the Discrete Fourier Transform, (DFT) and then show how the FFT computes the DFT and its inverse in $O(n \lg n)$.

The author then proves cancellation Lemma, halving Lemma and summation Lemma. The author also define and prove Convolution theorem.

The author then provides two efficient FFT implementations, an iterative FFT implementation and a parallel FFT circuit.