Chapter outline

Section 30.1 presents two ways to represent polynomials: the coefficient representation and the point-value representation. The straightforward methods for multiplying polynomials -equations (30.1) and (30.2) -take Θ(n²) time when the polynomials are represented in coefficient form, but only Θ(n) time when they are represented in point-value form. We can, however, multiply polynomials using the coefficient representation in only Θ(n lg n) time by converting between the two representations. To see why this works, we must first study complex roots of unity, which we do in Section 30.2. Then, we use the FFT and its inverse, also described in Section 30.2, to perform the conversions. Section 30.3 shows how to implement the FFT quickly in both serial and parallel models.

This chapter uses complex numbers extensively, and the symbol i will be used exclusively to denote .