Chapter 30: Polynomials and the FFT

The straightforward method of adding two polynomials of degree n takes Θ(n) time, but the straightforward method of multiplying them takes Θ(n²) time. In this chapter, we shall show how the Fast Fourier Transform, or FFT, can reduce the time to multiply polynomials to Θ(n lg n).

The most common use for Fourier Transforms, and hence the FFT, is in signal processing. A signal is given in the time domain: as a function mapping time to amplitude. Fourier analysis allows us to express the signal as a weighted sum of phase-shifted sinusoids of varying frequencies. The weights and phases associated with the frequencies characterize the signal in the frequency domain. Signal processing is a rich area for which there are several fine books; the chapter notes reference a few of them.

Polynomials

A polynomial in the variable x over an algebraic field F is a representation of a function A(x) as a formal sum:

We call the values a₀, a₁,..., a_n-1 the coefficients of the polynomial. The coefficients are drawn from a field F, typically the set C of complex numbers. A polynomial A(x) is said to have degree k if its highest nonzero coefficient is a_k. Any integer strictly greater than the degree of a polynomial is a degree-bound of that polynomial. Therefore, the degree of a polynomial of degree-bound n may be any integer between 0 and n - 1, inclusive.

There are a variety of operations we might wish to define for polynomials. For polynomial addition, if A(x) and B(x) are polynomials of degree-bound n, we say that their sum is a polynomial C(x), also of degree-bound n, such that C(x) = A(x) + B(x) for all x in the underlying field. That is, if

and

then

where c_j = a_j + b_j for j = 0, 1,..., n - 1. For example, if we have the polynomials A(x) = 6x³ + 7x² - 10x + 9 and B(x) = -2x³ + 4x - 5, then C(x) = 4x³ + 7x² - 6x + 4.

For polynomial multiplication, if A(x) and B(x) are polynomials of degree-bound n, we say that their product C(x) is a polynomial of degree-bound 2n - 1 such that C(x) = A(x) B(x) for all x in the underlying field. You probably have multiplied polynomials before, by multiplying each term in A(x) by each term in B(x) and combining terms with equal powers. For example, we can multiply A(x) = 6x³ + 7x² - 10x + 9 and B(x) = -2x³ + 4x - 5 as follows:

Another way to express the product C(x) is

(30.1)

where

(30.2)

We shall nevertheless speak of the degree-bound of C as being the sum of the degree-bounds of A and B, since if a polynomial has degree-bound k it also has degree-bound k + 1.