Student Center | Instructor's Center | Introduction to Algorithms | Home

Introduction to Algorithms, 2/e

Thomas H. Cormen, Dartmouth College
Charles E. Leiserson, Massachusetts Institute of Technology
Ronald L. Rivest, Massachusetts Institute of Technology
Clifford Stein, Columbia University

Polynomials and the FFT

Glossary

polynomial addition	if A(x) and B(x) are polynomials of degree-bound n, then 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. (See page 822)



polynomial multiplication	if A(x) and B(x) are polynomials of degree-bound n, then their product is a polynomial C(x) of degree-bound 2n -1 such that C(x) = A(x)B(x) for all x in the underlying field. (See page 823)



evaluating	operation consists of computing the value of A(x₀) on the polynomial A(x) at a given point x₀. (See page 824)



convolution	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 is also called the convolution of the input vectors a and b, denoted c = a ⊗ b. (See page 825)



point-value representation	of a polynomial A(x) of degree-bound n is a set of n point-value pairs {(x₀, y₀), (x₁, y₁), . . . , (x_{n - 1}, y_{n - 1})} such that all of the x_k are distinct and y_k = A(x_k) for k = 0, 1, . . . , n - 1. (See page 825)



interpolation	the inverse of evaluation, determining the coefficient form of a polynomial from a point-value representation. (See page 825)



Cartesian sum	Consider two sets Aand B, each having n integers in the range from 0 to 10n. The Cartesian sum is defined by C = {x + y : x ⊆ A and y ⊆ B}. (See page 830)



complex nth root of unity	a complex number ω such that ωⁿ = 1. There are exactly n complex nth roots of unity: e^2πkk/n for k = 0, 1, . . . , n - 1. (See page 830)



principal nth root of unity	ω_n = e^2πi/n is called the principal nth root of unity; all of the other complex nth roots of unity are powers of ω_n. (See page 831)



Discrete Fourier Transform (DFT)	The vector y = (y₀, y₁, . . . , y_{n - 1}) is the Discrete Fourier Transform (DFT) of the coefficient vector a = (a₀, a₁, . . . , a_{n - 1}). We also write y = DFT_n(a). (See page 833)



Toeplitz matrix	an n x n matrix A = (a_ij) such that a_ij = a_{i-1, j-1} for i = 2, 3, . . . , n and j = 2, 3, . . . , n. (See page 844)

2002 McGraw-Hill Higher Education
Any use is subject to the Terms of Use and Privacy Policy.
McGraw-Hill Higher Education is one of the many fine businesses of The McGraw-Hill Companies.