Polynomials And The Fft
Introduction: The straightforward method of adding two polynomials of degree n takes Θ(n) time, but the straightforward method of multiplying them takes Θ(n2) 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 a0, a1,..., an-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 ak. 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
where cj = aj bj for j = 0, 1,..., n - 1. For example, if we have the polynomials A(x) = 6x3 7x2 - 10x 9 and B(x) = -2x3 4x - 5, then C(x) = 4x3 7x2 - 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) = 6x3 7x2 - 10x 9 and B(x) = -2x3 4x - 5 as follows:
Another way to express the product C(x) is
| (30.1) |
 |
where
| (30.2) |
 |
|
Note that degree(C) = degree(A) degree(B), implying |
||
|
degree-bound(C) |
= |
degree-bound(A) degree-bound(B) - 1 |
|
≤ |
degree-bound(A) degree-bound(B). |
|
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.