Representing polynomials

Representing polynomials

A polynomial in the variable x over an algebraic field F represents a function A(x) as a formal sum:

, the values a₀, a₁, . . . ,a_n-1 the coefficients of the polynomial.

A polynomial A(x) has degree k if its highest nonzero coefficient is a_k i.e, degree(A) = k. 

Any integer strictly greater than the degree of a polynomial is degree-bound of that polynomial.

Polynomials can be represented using

•          the coefficient and
•          point-value representations of polynomials.

1. Coefficient representation: A coefficient representation of a polynomial 

, of degree bound ‘n’ is a vector of coefficients a = (a₀, a₁, . . . ,a_n-1). 

Example: A(𝑥) = 6𝑥³+7𝑥²−10𝑥+9  coefficients of A(x) are (9,−10,7,6).

The coefficient representation is convenient for certain operations on polynomials.

The operation of evaluating the polynomial (𝑥) at point 𝑥₀ consists of computing the value of 𝐴(𝑥_0­). Evaluation takes time θ(𝑛) using Horner’s rule 𝐴(𝑥₀)=𝑎₀+𝑥₀(𝑎₁+𝑥₀(𝑎₂+⋯+𝑥₀(𝑎_𝑛−2+𝑥₀ ­(𝑎_𝑛−1 ))⋯)).

Adding two polynomials represented by the coefficient vectors 𝑎=(𝑎₀,𝑎₁,…,𝑎_𝑛−1) and 𝑏=(𝑏₀,𝑏₁,…,𝑏_𝑛−1) takes time Θ(𝑛). Sum is the coefficient vector 𝑐=(𝑐₀,𝑐₁,…,𝑐_𝑛−1), where 𝑐_𝑗=𝑎_𝑗+𝑏_𝑗 for 𝑗=0,1,…,𝑛−1.

Example:

𝐴𝑥= 6𝑥³ + 7𝑥² − 10𝑥 + 9             (9,−10,7,6)

𝐵𝑥=− 2𝑥³ + 4𝑥 − 5                      (−5,4,0,−2)

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

(𝑥)= 4𝑥³ + 7𝑥² − 6𝑥 + 4              (4,−6,7,4)

2. Point-Value Representation: A point-value representation of a polynomial 𝐴(𝑥) of degree-bound 𝑛 is a set of 𝑛 point-value pairs {(𝑥₀,𝑦₀),(𝑥₁,𝑦₁),…,(𝑥_𝑛−1,𝑦_𝑛−1)} such that all of the 𝑥_𝑘 are distinct and 𝑦_𝑘=𝐴(𝑥_𝑘) for 𝑘=0,1,…,𝑛−1.

 Example: A(𝑥) =𝑥³−2𝑥+1

Using Horner’s method, 𝒏-point evaluation takes time θ(𝑛²).

The inverse of evaluation—determining the coefficient form of a polynomial from a point-value representation—is interpolation.

For any set {(𝑥0,𝑦0),(𝑥1,𝑦1),…,(𝑥𝑛−1,𝑦𝑛−1)} of 𝑛 point-value pairs such that all the 𝑥𝑘 values are distinct, there is a unique polynomial 𝐴(𝑥) of degree-bound 𝑛 such that 𝑦𝑘=𝐴(𝑥𝑘) for 𝑘=0,1,…,𝑛−1.

Using Lagrange’s formula, interpolation takes time θ(𝑛²).

Lagrange’s formula

Example: Using Lagrange’s formula, we interpolate the point-value representation {(0,1),(1,0),(2,5),(3,22)}.

In point-value form, addition 𝐶(𝑥)=𝐴(𝑥)+𝐵(𝑥) is given by 𝐶(𝑥_𝑘)=𝐴(𝑥_𝑘)+𝐵(𝑥_𝑘) for any point 𝑥_𝑘.

𝐴 and 𝐵 are evaluated for the same 𝑛 points. The time to add two polynomials of degree-bound 𝑛 in point-value form is θ(𝑛).

Example:  Add (𝑥)=𝐴(𝑥)+𝐵(𝑥) in point-value form 

In point-value form, multiplication 𝐶(𝑥)=𝐴(𝑥)𝐵(𝑥)  is given by 𝐶(𝑥_𝑘)=𝐴(𝑥_𝑘)𝐵(𝑥_𝑘) for any point 𝑥_𝑘. If 𝐴 and 𝐵 are of degree-bound 𝑛, then 𝐶 is of degree-bound 2𝑛.

Need to start with “extended” point-value forms for 𝐴 and 𝐵 consisting of 2𝑛 point-value pairs each.

The time to multiply two polynomials of degree-bound 𝑛 in point-value form is θ(𝑛). 

Example:  Multiply 𝐶𝑥=𝐴(𝑥)𝐵(𝑥) in point-value form

Given two input polynomials in extended point-value form, the time to multiply them to obtain the point value form of the result is θ(n), which is much less than the time required to multiply polynomials in coefficient form θ(n²).

A graphical outline of an efficient polynomial-multiplication process is given below. Representations on the top are in coefficient form, while those on the bottom are in point-value form.