 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 degreebound n, then their sum is a polynomial C(x), also of degreebound 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 degreebound n, then their product is a polynomial C(x) of degreebound 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_{0}) on the polynomial A(x) at a given point x_{0}.
(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)
    pointvalue representation  of a polynomial A(x) of degreebound n is a set of n pointvalue pairs {(x_{0}, y_{0}), (x_{1}, y_{1}), . . . , (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 pointvalue 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: 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_{0}, y_{1}, . . . , y_{n  1}) is the Discrete Fourier Transform (DFT) of the coefficient vector a = (a_{0}, a_{1}, . . . , 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_{i1, j1} for i = 2, 3, . . . , n and j = 2, 3, . . . , n.
(See page 844)

