Student Center
 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 Choose one...Chapter 1Chapter 2Chapter 3Chapter 4Chapter 5Chapter 6Chapter 7Chapter 8Chapter 9Chapter 10Chapter 11Chapter 12Chapter 13Chapter 14Chapter 15Chapter 16Chapter 17Chapter 18Chapter 19Chapter 20Chapter 21Chapter 22Chapter 23Chapter 24Chapter 25Chapter 26Chapter 27Chapter 28Chapter 29Chapter 30Chapter 31Chapter 32Chapter 33Chapter 34Chapter 35Appendix AAppendix BAppendix C Chapter Overview Glossary PowerPoint Slides Algorithm Pseudocode FeedbackHelp Center

Introduction to Algorithms, 2/e

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(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 = 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{(x0, y0), (x1, y1), . . . , (xn - 1, yn - 1)}such that all of the xk are distinct andyk = 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 : x ⊆ A and y ⊆ B}. (See page 830) complex nth root of unity a complex number ω such thatωn = 1.There are exactly n complex nth roots of unity: e2πkk/n for k = 0, 1, . . . , n - 1. (See page 830) principal nth root of unity ωn = e2πi/nis 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)