McGraw-Hill OnlineMcGraw-Hill Higher EducationLearning Center
Student Center | Instructor's Center | Introduction to Algorithms | Home
Glossary A-B
Glossary B-D
Glossary D-F
Glossary F-J
Glossary J-M
Glossary M-O
Glossary O-P
Glossary P-S
Glossary S-T
Glossary T-Z
Chapter Overview
PowerPoint Slides
Algorithm Pseudocode
Help Center

small text cover image
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


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(x0) on the polynomial
A(x) at a given point x0.
(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 = ab.
(See page 825)
point-value representation  of a polynomial A(x) of degree-bound n is a set of n point-value pairs

{(x0, y0), (x1, y1), . . . , (xn - 1, yn - 1)}

such that all of the xk are distinct and

yk = A(xk)

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 : xA and yB}.
(See page 830)
complex nth root of unity  a complex number ω such that

ωn = 1.

There are exactly n complex nth roots of unity: ekk/n for
k = 0, 1, . . . , n - 1.

(See page 830)
principal nth root of unity  ωn = ei/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 = (y0, y1, . . . , yn - 1) is the Discrete Fourier Transform (DFT) of the coefficient vector a = (a0, a1, . . . , an - 1). We also write
y = DFTn(a).
(See page 833)
Toeplitz matrix  an n x n matrix A = (aij) such that aij = ai-1, j-1 for i = 2, 3, . . . , n and
j = 2, 3, . . . , n.
(See page 844)