A * polynomial* in the variable

We call *n *the * degree-bound* of the polynomial, and we call the values

There are a variety of operations we might wish to define for polynomials. For * polynomial addition*, if

For * polynomial multiplication*, if

6x^{3 }+ 7x^{2 }- 10x+ 9

- 2x^{3}+ 4x- 5

-------------------------

- 30x^{3 }- 35x^{2 }+ 50x- 45

24x^{4 }+ 28x^{3 }- 40x^{2 }+ 36x

- 12x^{6 }- 14x^{5 }+ 20x^{4}- 18x^{3}

---------------------------------------------

- 12x^{6 }- 14x^{5 }+ 44x^{4 }- 20x^{3 }- 75x^{2 }+ 86x- 45

Another way to express the product *C*(*x*) is

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).

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

A * coefficient representation* of a polynomial of degree-bound

The coefficient representation is convenient for certain operations on polynomials. For example, the operation of * evaluating* the polynomial

A(x_{0}) =a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+^{...}+x_{0}(a-2+_{n}x_{0}(a-1))_{n}^{...})).

Now, consider the multiplication of two degree-bound *n* polynomials *A*(*x*) and *B*(*x*) represented in coefficient form. If we use the method described by equations (32.1) and (32.2), polynomial multiplication takes time (*n*^{2}), since each coefficient in the vector* a *must be multiplied by each coefficient in the vector *b*. 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 *c*, given by equation (32.2), is also called the * convolution* of the input vectors

A* point-value representation*

{(x_{0},y_{0}), (x_{1},y_{1}), . . ., (x-1,_{n}y-1)}_{n}

such that all of the *x _{k}* are distinct and

y=_{k}A(x)_{k}

The inverse of evaluation--determining the coefficient form of a polynomial from a point-value representation--is called * interpolation*. 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.

a = V(x_{0}, x_{1}, . . ., x_{n-1})^{-1}y.

A faster algorithm for *n*-point interpolation is based on **Lagrange's formula:**

{(x_{0},y_{0}), (x_{1},y_{1}), . . ., (x-1,_{n}y-1)} ,_{n}

{(x_{0}, y'_{0}), (x_{1}, y'_{1}), . . ., (x-1, y'_{n}-1)}_{n}

(note that *A* and *B* are evaluated at the *same n* points), then a point-value representation for *C* is

{(x_{0}, y_{0 }+ y'_{0}), (x_{1}, y_{1}+y'_{1}), . . ., (x_{n-1}, y_{n-1}+y'_{n-1})}.

The time to add two polynomials of degree-bound *n* in point-value form is thus (*n*).

{(x_{0},y_{0}),(x_{1},y_{1}),...,(x_{2n-1},y_{2n-1})},

and a corresponding extended point-value representation for *B*,

{(x_{0},y'_{0}),(x_{1},y'_{1}),...,(x_{2n-1},y'_{2n-1})},

then a point-value representation for C is

{(x_{0},y_{0}y'_{0}),(x_{1},y_{1}y'_{1}),...,(x_{2n-1},y_{2n-1}y'_{2n-1})}.

Can we use the linear-time multiplication method for polynomials in point-value form to expedite polynomial multiplication in coefficient form? The answer hinges on our ability to convert a polynomial quickly from coefficient form to point-value form (evaluate) and vice-versa (interpolate).

Evaluating a polynomial *A*(*x*) of degree-bound *n* at a given point *x*_{0} can also be done by dividing *A*(*x*) by the polynomial (*x* - *x*_{0}*) *to obtain a quotient polynomial *q*(*x*) of degree-bound *n* - 1 and a remainder *r*, such that

A(x) =q(x)(x-x_{0}) +r.

Consider two sets *A* and *B*, each having *n* integers in the range from 0 to 10*n*. We wish to compute the * Cartesian sum* of

C= {x+y:xAandyB}.

A * complex nth root of unity* is a complex number

w= 1 .^{n}

e= cos(^{iu}u) +isin(u).

Figure 32.2 shows that the *n *complex roots of unity are equally spaced around the circle of unit radius centered at the origin of the complex plane. The value

w=_{n}e^{2}i/n

The *n* complex *n*th roots of unity,

For any integers *n* 0, *k* 0, and *d* > 0,

* Proof* The lemma follows directly from equation (32.6), since

* Proof* The proof is left as Exercise 32.2-1.

For any integer *n* 1 and nonnegative integer *k* not divisible by *n*,

* Proof* Because equation (3.3) applies to complex values,

Recall that we wish to evaluate a polynomial

The vector *y* = (*y*_{0}, *y*_{1}, . . . , *y _{n}*-1) is the

By using a method known as the * Fast Fourier Transform (FFT),* which takes advantage of the special properties of the complex roots of unity, we can compute

A^{[0]}(x) =a_{0}+a_{2}x+a_{4}x^{2}+ +a-2_{n}x/2-1,^{n}

A^{[1]}(x) =a_{1}+a_{3}x+a_{5}x^{2}+ +a-1_{n}x/2-1.^{n}

A(x) =A^{[0]}(x^{2}) +xA^{[1]}(x^{2}),

so that the problem of evaluating *A*(*x*) at reduces to

1. evaluating the degree-bound *n*/2 polynomials *A*^{[0]}(*x*) and *A*^{[1]}(*x*) at the points

2. combining the results according to equation (32.9).

By the halving lemma, the list of values (32.10) consists not of *n* distinct values but only of the *n*/2 complex (*n*/2)th roots of unity, with each root occurring exactly twice. Therefore, the polynomials *A*^{[0]} and *A*^{[1]} of degree-bound *n*/2 are recursively evaluated at the *n*/2 complex (*n*/2)th roots of unity. These subproblems have exactly the same form as the original problem, but are half the size. We have now successfully divided an *n*-element DFT* _{n}* computation into two

or, since by the cancellation lemma,

T(n) = 2T(n/2) + (n)

= (nlgn) .

We now complete the polynomial multiplication scheme by showing how to interpolate the complex roots of unity by a polynomial, which enables us to convert from point-value form back to coefficient form. We interpolate by writing the DFT as a matrix equation and then looking at the form of the matrix inverse.

For *j, k* = 0, 1, . . . , *n* - 1, the (*j, k*) entry of .

* Proof *We show that , the

Given the inverse matrix , we have that is given by

For any two vectors *a* and *b* of length *n*, where *n* is a power of 2,

Compute the DFT of the vector (0, 1, 2, 3).

Do Exercise 32.1-1 by using the (*n *lg *n*)-time scheme.

Write pseudocode to compute in (*n *lg *n*) time.

The * chirp transform* of a vector

to view the chirp transform as a convolution.)

We first note that the **for** loop of lines 10-13 of RECURSIVE-FFT involves computing the value twice. In compiler terminology, this value is known as a * common subexpression*. We can change the loop to compute it only once, storing it in a temporary variable

The operation in this loop, multiplying *w* (which is equal to , storing the product into *t*, and adding and subtracting *t* from , is known as a **butterfly*** operation* and is shown schematically in Figure 32.3.

1fors1tolgn

2do fork0ton- 1by2^{s}

3docombine the two 2-1 -element DFT's in^{s}

A[k . . k+ 2-1 - 1] and^{s}A[k + 2-1^{s}. . k +2- 1]^{s}

into one 2-element DFT in^{s}A[k . . k +2- 1]^{s}

FFT-BASE(a)

1nlength[a]nis a power of 2.

2fors1tolgn

3dom2^{s}

4w_{m}e^{2}i/m

5fork0ton- 1bym

6dow1

7forj0tom/2 - 1

8dotwA[k + j + m/2]

9uA[k + j]

10A[k + j]u + t

11A[k + j + m /2]u - t

12www_{m}

ITERATIVE-FFT(a)

1 BIT-REVERSE-COPY (a, A)

2nlength[a]nis a power of 2.

3fors1tolgn

4dom2^{s}

5we_{m }^{2}^{i/m}

6w1

7forj0tom/2 - 1

8do forkjton- 1bym

9dotwA[k+m/2]

10uA[k]

11A[k]u+t

12A[k+m/2]u-t

13www_{m}

14returnA

BIT-REVERSE-COPY(a, A)

1nlength[a]

2fork0ton- 1

3doA[rev(k)]a_{k}

We can exploit many of the properties that allowed us to implement an efficient iterative FFT algorithm to produce an efficient parallel algorithm for the FFT. (See Chapter 29 for a description of the combinational-circuit model.) The combinational circuit PARALLEL-FFT that computes the FFT on *n* inputs is shown in Figure 32.5 for *n* = 8. The circuit begins with a bi-reverse permutation of the inputs, followed by lg *n* stages, each stage consisting of *n*/2 butterflies executed in parallel. The depth of the circuit is therefore (lg *n*).

Show how ITERATIVE-FFT computes the DFT of the input vector (0, 2, 3, -1, 4, 5, 7, 9).

32-1 Divide-and-conquer multiplication

* a.* Show how to multiply two linear polynomials

A * Toeplitz matrix* is an

* a. *Is the sum of two Toeplitz matrices necessarily Toeplitz? What about the product?

32-3 Evaluating all derivatives of a polynomial at a point

Given a polynomial *A*(*x*) of degree-bound *n*, its *t*th derivative is defined by

* a.* Given coefficients

show how to compute *A*^{(t) }(*x*_{0}), for *t* = 0, 1, . . . , *n* - 1, in *O*(*n*) time.

32-4 Polynomial evaluation at multiple points

We have observed that the problem of evaluating a polynomial of degree-bound *n* - 1 at a single point can be solved in *O*(*n*) time using Horner's rule. We have also discovered that such a polynomial can be evaluated at all *n* complex roots of unity in *O*(*n* lg *n*) time using the FFT. We shall now show how to evaluate a polynomial of degree-bound *n* at *n* arbitrary points in *O*(*n* lg^{2} *n*) time.

(3x^{3}+x^{2}- 3x+ 1) mod (x^{2}+x+ 2) = 5x- 3.

* a.* Prove that

* b.* Prove that

* d.* Give an

32-5 FFT using modular arithmetic

As defined, the Discrete Fourier Transform requires the use of complex numbers, which can result in a loss of precision due to round-off errors. For some problems, the answer is known to contain only integers, and it is desirable to utilize a variant of the FFT based on modular arithmetic in order to guarantee that the answer is calculated exactly. An example of such a problem is that of multiplying two polynomials with integer coefficients. Exercise 32.2-6 gives one approach, using a modulus of length (*n*) bits to handle a DFT on *n* points. This problem gives another approach that uses a modulus of the more reasonable length *O*(lg *n*); it requires that you understand the material of Chapter 33. Let *n* be a power of 2.

Let *g* be a generator of , and let *w* = *g ^{k}* mod