Next: The Chinese Remaindering Algorithm Up: Modular Algorithms and interpolation Previous: Modular Algorithms and interpolation

## Evaluation, interpolation

Let be a field and let u = (u0,..., un-1) be a sequence of pairwise distinct elements of .

Remark 7   A polymomial in [x] with degree n - 1, say

 f  =  f0 + f1x + ... + fn-1xn-1 (26)

can be evaluated at x = x0 using Horner's rule

 f (x0)  =  ( ... (fn-1x0 + fn-2)x0 + ... + f1)x0 + f0 (27)

with n - 1 additions and n - 1 multiplications leading to 2n - 2 operations in the base field . The proof is easy by induction on n 1.

Definition 2   For i = 0 ... n - 1 the i-th Lagrange interpolant is the polynomial

 Li(u)  = (28)

with the property that

 Li(uj) = (29)

Proposition 5   Let v0,..., vn-1 be in . There is a unique polynomial f [x] with degree less than n and such that

 f (ui) = vi  for  i = 0 ... n - 1. (30)

Moreover this polynomial is given by

 f  =   vi Li(u). (31)

Proof. Clearly the polynomial f of Relation (31) satisfies Relation (30). Hence the existence is clear. The unicity follows from the fact that the difference of two such polynomials has
• degree less than n and
• n roots
hence is the zero polynomial.

Proposition 6   Evaluating a polynomial f [x] of degree less than n at n distinct points u0,..., un-1 or computing an interpolating polynomial at these points can be done in (n2) operations in .

Proof. We saw in Remark 7 that evaluating the polynomial f of degree n at one point costs 2n - 2 operations in . So evaluating f at u0,..., un-1 amounts to 2n2 - 2n. Let us prove now that interpolating a polynomial at u0,..., un-1 can be done in (n2) operations in . We first need to estimate the cost of computing the i-th interpolant Li(u). Consider m0m1, m0m1m2, ... m = m0 ... mn-1 where mi is the monic polynomial mi = x - ui. Let pi = m0m1 ... mi-1 and qi = m/mi for i = 1 ... n. We have

 Li(u)  = (32)

To estimate the cost of computing the Li(u)'s let us start with that of m. Computing the product of the monic polynomial pi = m0m1 ... mi-1 of degree i by the monic polynomial mi = x-ui of degree 1 costs
• i multiplications (in the field ) to get - ui pi plus
• i - 1 additions (in the field ) to add - ui pi (of degree i) to x pi (of degree i + 1 but without constant term)
leading to i - 1. Hence computing p2,..., pn = m amounts to

 2 i - 1 = 2 i + 1 = 2i  +  n - 1 = 2 n (n - 1)/2  +  n - 1 = (n - 1)(n + 1)
(33)

Computing qi implies a division-with-remainder of the polynomial m of degree n by the polynomial mi of degree 1. This division will have n - 1 + 1 steps, each step requiring 2 operations in . Hence computing all qi's amounts to n 2 n. Since qi has degree n - 1 computing each qi(ui)'s amounts to 2n - 2 operations in the base field (from Remark 7). Then computing all qi(ui)'s amounts to 2n2 - 2n. Then computing each Li(u) = qi/qi(ui) from the qi's and qi(ui)'s costs n. Therefore computing all Li(u)'s from scratch amounts to (n - 1)(n + 1) + 2 n2 + 2n2 - 2n + n2 = 6n2 - 2n - 1.

Computing f from the Li(u)'s requires

• to multiply each Li(u) (which is a polynomial of degree n - 1) by the number vi leading to n2 operations in and
• to add these vi Li(u) leading to n - 1 additions of polynomials of degree at most n - 1 costing (n - 1)n operations in
amounting to n2 - n. Finally the total cost is 6n2 - 2n - 1 + 2 n2 - n = 8 n2 - 3 n - 1

Remark 8   We consider the map

 E : (34)

This is just the map corresponding to evaluation of polynomials of degree less than n at points u0,..., un-1. It is obvious that E is -linear and it can be represented by the Vandermonde matrix

 VDM(u0,..., un-1)  = (35)

From the above discussion, this matrix is invertible iff ui uj for all 0 i < j n - 1. To conclude observe that both evaluation and interpolation are linear maps between coefficients and value vectors.

Next: The Chinese Remaindering Algorithm Up: Modular Algorithms and interpolation Previous: Modular Algorithms and interpolation
Marc Moreno Maza
2004-04-27