📄 chap32.htm
字号:
<HTML><HEAD>
<TITLE>Intro to Algorithms: CHAPTER 32: POLYNOMIALS AND THE FFT</TITLE></HEAD><BODY BGCOLOR="#FFFFFF">
<a href="chap33.htm"><img align=right src="../../images/next.gif" alt="Next Chapter" border=0></A>
<a href="toc.htm"><img align=right src="../../images/toc.gif" alt="Return to Table of Contents" border=0></A>
<a href="chap31.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A>
<h1><a name="098a_1afd">CHAPTER 32: POLYNOMIALS AND THE FFT<a name="098a_1afd"></h1><P>
The straightforward method of adding two polynomials of degree <I>n </I>takes <img src="../images/bound.gif">(<I>n</I>) time, but the straightforward method of multiplying them takes <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>) time. In this chapter, we shall show how the Fast Fourier Transform, or FFT, can reduce the time to multiply polynomials to <img src="../images/bound.gif">(<I>n</I>l<I> n</I>).<P>
Polynomials<P>
<a name="098a_1af3">A <I><B>polynomial</I></B> in the variable <I>x</I> over an algebraic field <I>F </I>is a function <I>A</I>(<I>x</I>) that can be represented as follows:<P>
<img src="776_a.gif"><P>
<a name="098a_1af4"><a name="098a_1af5"><a name="098a_1af6">We call <I>n </I>the <I><B>degree-bound</I></B> of the polynomial, and we call the values <I>a</I><SUB>0</SUB>, <I>a</I><SUB>1</SUB>, . . ., <I>a<SUB>n</I> - 1 </SUB>the <I><B>coefficients</I></B> of the polynomial. The coefficients are drawn from the field <I>F</I>, typically the set <B>C</B> of complex numbers. A polynomial <I>A</I>(<I>x</I>) is said to have <I><B>degree</I></B> <I>k </I>if its highest nonzero coefficient is <I>a<SUB>k</I></SUB>. The degree of a polynomial of degree-bound <I>n</I> can be any integer between 0 and <I>n</I> - 1, inclusive. Conversely, a polynomial of degree <I>k</I> is a polynomial of degree-bound <I>n </I>for any <I>n</I> > <I>k</I>.<P>
<a name="098a_1af7"><a name="098a_1af8"><a name="098a_1af9">There are a variety of operations we might wish to define for polynomials. For <I><B>polynomial addition</I></B>, if <I>A</I> (<I>x</I>) and <I>B</I> (<I>x</I>) are polynomials of degree-bound <I>n</I>, we say that their <I><B>sum</I></B> is a polynomial <I>C</I> (<I>x</I>), also of degree-bound <I>n</I>, such that <I>C</I> (<I>x</I>)<I> = A</I> (<I>x</I>)<I> + B</I> (<I>x</I>) for all <I>x</I> in the underlying field. That is, if<P>
<img src="776_b.gif"><P>
and<P>
<img src="776_c.gif"><P>
then<P>
<img src="777_a.gif"><P>
where <I>c<SUB>j</I></SUB> = <I>a<SUB>j</SUB> </I>+ <I>b<SUB>j</SUB> </I>for <I>j </I>= 0,1, . . .,<I>n </I>- 1. For example, if <I>A</I>(<I>x</I>) = 6<I>x</I><SUP>3 </SUP>+ 7x<SUP>2 </SUP>- 10<I>x </I>+ 9 and <I>B</I>(<I>x</I>) = -2<I>x</I><SUP>3</SUP>+ 4<I>x </I>- 5, then <I>C</I>(<I>x</I>) = 4<I>x</I><SUP>3 </SUP>+ 7<I>x</I><SUP>2 </SUP>- 6<I>x </I>+ 4.<P>
<a name="098a_1afa"><a name="098a_1afb"><a name="098a_1afc">For <I><B>polynomial multiplication</I></B>, if <I>A</I>(<I>x</I>) and <I>B</I>(<I>x</I>) are polynomials of degree-bound <I>n</I>, we say that their <I><B>product</I></B> <I>C</I>(<I>x</I>) is a polynomial of degree-bound 2<I>n </I>- 1 such that <I>C</I>(<I>x</I>) = <I>A</I>(<I>x</I>)<I>B</I>(<I>x</I>) for all <I>x </I>in the underlying field. You have probably multiplied polynomials before, by multiplying each term in <I>A</I>(<I>x</I>) by each term in <I>B</I>(<I>x</I>) and combining terms with equal powers. For example, we can multiply <I>A</I>(<I>x</I>) = 6<I>x</I><SUP>3 </SUP>+ 7<I>x</I><SUP>2 </SUP>- 10<I>x </I>+ 9 and <I>B</I>(<I>x</I>) = -2<I>x</I><SUP>3 </SUP>+ 4<I>x </I>- 5 as follows:<P>
<pre> 6<I>x</I><SUP>3 </SUP>+ 7<I>x</I><SUP>2 </SUP>- 10<I>x</I> + 9</sub></sup></pre><P>
<pre> - 2<I>x</I><SUP>3</SUP> + 4<I>x</I> - 5</sub></sup></pre><P>
<pre> -------------------------</sub></sup></pre><P>
<pre> - 30<I>x</I><SUP>3 </SUP>- 35<I>x</I><SUP>2 </SUP>+ 50<I>x</I> - 45</sub></sup></pre><P>
<pre> 24<I>x</I><SUP>4 </SUP>+ 28<I>x</I><SUP>3 </SUP>- 40<I>x</I><SUP>2 </SUP>+ 36<I>x</I></sub></sup></pre><P>
<pre>- 12<I>x</I><SUP>6 </SUP>- 14<I>x</I><SUP>5 </SUP>+ 20<I>x</I><SUP>4</SUP> - 18<I>x</I><SUP>3</sub></sup></pre><P>
<pre>---------------------------------------------</sub></sup></pre><P>
<pre>- 12<I>x</I><SUP>6 </SUP>- 14<I>x</I><SUP>5 </SUP>+ 44<I>x</I><SUP>4 </SUP>- 20<I>x</I><SUP>3 </SUP>- 75<I>x</I><SUP>2 </SUP>+ 86<I>x</I> - 45</sub></sup></pre><P>
Another way to express the product <I>C</I>(<I>x</I>) is<P>
<img src="777_b.gif"><P>
<h4><a name="098a_1afe">(32.1)<a name="098a_1afe"></sub></sup></h4><P>
where<P>
<img src="777_c.gif"><P>
<h4><a name="098a_1aff">(32.2)<a name="098a_1aff"></sub></sup></h4><P>
<pre>Note that degree(<I>C</I>) = degree(<I>A</I>) + degree(<I>B</I>), implying</sub></sup></pre><P>
<pre>degree-bound(<I>C</I>) = degree-bound(<I>A</I>) + degree-bound(<I>B</I>) - 1</sub></sup></pre><P>
<pre><img src="../images/lteq12.gif"> degree-bound(<I>A</I>) + degree-bound(<I>B</I>).</sub></sup></pre><P>
We shall nevertheless speak of the degree-bound of <I>C</I> as being the sum of the degree-bounds of <I>A</I> and <I>B</I>, since if a polynomial has degree-bound <I>k</I> it also has degree-bound <I>k</I> + 1.<P>
Chapter outline<P>
Section 32.1 presents two ways to represent polynomials: the coefficient representation and the point-value representation. The straightforward methods for multiplying polynomials--equations (32.1) and (32.2)--take <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>) time when the polynomials are represented in coefficient form, but only <img src="../images/bound.gif">(<I>n</I>) time when they are represented in point-value form. We can, however, multiply polynomials using the coefficient representation in only <img src="../images/bound.gif">(<I>n</I> lg <I>n</I>) 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 32.2. Then, we use the FFT and its inverse, also described in Section 32.2, to perform the conversions. Section 32.3 shows how to implement the FFT quickly in both serial and parallel models.<P>
This chapter uses complex numbers extensively, and the symbol <I>i</I> will be used exclusively to denote <img src="778_a.gif">.<P>
<h1><a name="098c_0001">32.1 Representation of polynomials<a name="098c_0001"></h1><P>
The coefficient and point-value representations of polynomials are in a sense equivalent; that is, a polynomial in point-value form has a unique counterpart in coefficient form. In this section, we introduce the two representations and show how they can be combined to allow multiplication of two degree-bound <I>n</I> polynomials in <img src="../images/bound.gif">(<I>n </I>lg <I>n</I>) time.<P>
<h2>Coefficient representation</h2><P>
<a name="098d_1afd"><a name="098d_1afe">A <I><B>coefficient representation</I></B> of a polynomial <img src="778_b.gif"> of degree-bound <I>n</I> is a vector of coefficients <I>a</I> = (<I>a</I><SUB>0</SUB>, <I>a</I><SUB>1</SUB>, . . ., <I>a<SUB>n</I></SUB>-<SUB>1</SUB>). In matrix equations in this chapter, we shall generally treat vectors as column vectors.<P>
<a name="098d_1aff"><a name="098d_1b00"><a name="098d_1b01">The coefficient representation is convenient for certain operations on polynomials. For example, the operation of <I><B>evaluating</I></B> the polynomial <I>A</I>(<I>x</I>) at a given point <I>x</I><SUB>0</SUB> consists of computing the value of <I>A</I>(<I>x</I><SUB>0</SUB>). Evaluation takes time <img src="../images/bound.gif">(<I>n</I>) using <I><B>Horner's rule:</I></B><P>
<pre><I>A</I>(<I>x</I><SUB>0</SUB>) = <I>a</I><SUB>0</SUB> + <I>x</I><SUB>0</SUB>(<I>a</I><SUB>1</SUB>+<I>x</I><SUB>0</SUB>(<I>a</I><SUB>2</SUB>+ <SUP>...</SUP> +<I>x</I><SUB>0</SUB>(<I>a<SUB>n</I>-2</SUB>+<I>x</I><SUB>0</SUB>(<I>a<SUB>n</I>-1</SUB>))<SUP>...</SUP>)).</sub></sup></pre><P>
Similarly, adding two polynomials represented by the coefficient vectors <I>a</I> = (<I>a</I><SUB>0</SUB>, <I>a</I><SUB>1</SUB>, . . ., <I>a<SUB>n</I></SUB>-<SUB>1</SUB>) and <I>b</I> = (<I>b</I><SUB>0</SUB>, <I>b</I><SUB>1</SUB>, . . ., <I>b<SUB>n</I></SUB>-<SUB>1</SUB>) takes <img src="../images/bound.gif">(<I>n</I>) time: we just output the coefficient vector <I>c</I> = (<I>c</I><SUB>0</SUB>, <I>c</I><SUB>1</SUB>, . . ., <I>c<SUB>n</I></SUB>-<SUB>1</SUB>), where <I>c<SUB>j</I></SUB> = <I>a<SUB>j</I></SUB> + <I>b<SUB>j</I></SUB> for <I>j </I>= 0,1, . . . ,<I>n </I>- 1.<P>
<a name="098d_1b02"><a name="098d_1b03"><a name="098d_1b04">Now, consider the multiplication of two degree-bound <I>n</I> polynomials <I>A</I>(<I>x</I>) and <I>B</I>(<I>x</I>) represented in coefficient form. If we use the method described by equations (32.1) and (32.2), polynomial multiplication takes time <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>), since each coefficient in the vector<I> a </I>must be multiplied by each coefficient in the vector <I>b</I>. The operation of multiplying polynomials in coefficient form seems to be considerably more difficult than that of evaluating a polynomial or adding two polynomials. The resulting coefficient vector <I>c</I>, given by equation (32.2), is also called the <I><B>convolution</I></B> of the input vectors <I>a</I> and <I>b</I>, denoted <I>c</I> = <I>a </I><img src="../images/circx.gif"><I> b</I>. Since multiplying polynomials and computing convolutions are fundamental computational problems of considerable practical importance, this chapter concentrates on efficient algorithms for them.<P>
<P>
<h2>Point-value representation</h2><P>
<a name="098e_1b05"><a name="098e_1b06">A<I> <B>point-value representation</I></B><I> </I>of a polynomial <I>A</I>(<I>x</I>) of degree-bound <I>n</I> is a set of <I>n</I> <I><B>point-value pairs</I></B><P>
<pre>{(<I>x</I><SUB>0</SUB>, <I>y</I><SUB>0</SUB>), (<I>x</I><SUB>1</SUB>, <I>y</I><SUB>1</SUB>), . . ., (<I>x<SUB>n</I>-1</SUB>, <I>y<SUB>n</I>-1</SUB>)}</sub></sup></pre><P>
such that all of the <I>x<SUB>k</I></SUB> are distinct and<P>
<pre><I>y<SUB>k</I></SUB> = <I>A</I>(<I>x<SUB>k</I></SUB>)</sub></sup></pre><P>
<h4><a name="098e_1b0a">(32.3)<a name="098e_1b0a"></sub></sup></h4><P>
for <I>k</I> = 0, 1, . . ., <I>n</I> - 1. A polynomial has many different point-value representations, since any set of <I>n</I> distinct points <I>x</I><SUB>0</SUB>, <I>x</I><SUB>1</SUB>, . . ., <I>x<SUB>n</I>-1</SUB> can be used as a basis for the representation.<P>
Computing a point-value representation for a polynomial given in coefficient form is in principle straightforward, since all we have to do is select <I>n</I> distinct points <I>x</I><SUB>0</SUB>, <I>x</I><SUB>1</SUB>, . . ., <I>x<SUB>n</I>-1</SUB> and then evaluate <I>A</I>(<I>x<SUB>k</I></SUB>) for <I>k</I> = 0, 1, . . ., <I>n</I> - 1. With Horner<I><B></I></B>'s method, this <I>n</I>-point evaluation takes time <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>). We shall see later that if we choose the <I>x<SUB>k</I></SUB> cleverly, this computation can be accelerated to run in time <img src="../images/bound.gif">(<I>n </I>lg <I>n</I>).<P>
<a name="098e_1b07"><a name="098e_1b08">The inverse of evaluation--determining the coefficient form of a polynomial from a point-value representation--is called <I><B>interpolation</I></B>. The following theorem shows that interpolation is well defined, assuming that the degree-bound of the interpolating polynomial equals the number of given point-value pairs.<P>
<a name="098e_1b0b">Theorem 32.1<a name="098e_1b0b"><P>
For any set {(<I>x</I><SUB>0</SUB>, <I>y</I><SUB>0</SUB>), (<I>x</I><SUB>1</SUB>, <I>y</I><SUB>1</SUB>), . . ., (<I>x<SUB>n</I></SUB>-<SUB>1</SUB>, <I>y<SUB>n</I></SUB>-<SUB>1</SUB>)} of <I>n</I> point-value pairs, there is a unique polynomial <I>A</I>(<I>x</I>) of degree-bound <I>n</I> such that <I>y<SUB>k</I></SUB> = <I>A</I>(<I>x<SUB>k</I></SUB>) for <I>k </I>= 0, 1, . . ., <I>n</I> - 1.<P>
<I><B>Proof</I></B> The proof is based on the existence of the inverse of a certain matrix. Equation (32.3) is equivalent to the matrix equation<P>
<img src="779_a.gif"><P>
<h4><a name="098e_1b0c">(32.4)<a name="098e_1b0c"></sub></sup></h4><P>
The matrix on the left is denoted <I>V</I>(<I>x</I><SUB>0</SUB>, <I>x</I><SUB>1</SUB>, . . ., <I>x<SUB>n</I></SUB>-<SUB>1</SUB>) and is known as a Vandermonde matrix. By Exercise 31.1-10, this matrix has determinant<P>
<img src="779_b.gif"><P>
and therefore, by Theorem 31.5, it is invertible (that is, nonsingular) if the <I>x<SUB>k</I></SUB> are distinct. Thus, the coefficients <I>a<SUB>j</SUB> </I>can be solved for uniquely given the point-value representation:<P>
<pre>a = V(x<SUB>0</SUB>, x<SUB>1</SUB>, . . ., x<SUB>n-1</SUB>)<SUP>-1</SUP>y. </sub></sup></pre><P>
The proof of Theorem 32.1 describes an algorithm for interpolation based on solving the set (32.4) of linear equations. Using the LU decomposition algorithms of Chapter 31, we can solve these equations in time <I>O</I>(<I>n</I><SUP>3</SUP>).<P>
<a name="098e_1b09">A faster algorithm for <I>n</I>-point interpolation is based on <I><B>Lagrange's formula:</I></B><P>
<img src="780_a.gif"><P>
<h4><a name="098e_1b0d">(32.5)<a name="098e_1b0d"></sub></sup></h4><P>
You may wish to verify that the right-hand side of equation (32.5) is a polynomial of degree-bound <I>n</I> that satisfies <I>A</I>(<I>x<SUB>k</I></SUB>) = <I>y<SUB>k</I></SUB> for all <I>k</I>. Exercise 32.1-4 asks you how to compute the coefficients of <I>A</I> using Lagrange<I><B></I></B>'s formula in time <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>).<P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -