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

Evaluation, interpolation

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

Remark 7   A polymomial in $ \bf k$[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 $ \bf k$. The proof is easy by induction on n $ \geq$ 1.

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

Li(u)  =  $\displaystyle \Pi_{{{\mbox{\begin{scriptsize}$\begin{array}{c} 0 \leq j < n \\  j \neq i\end{array}$\end{scriptsize}}}}}^{{}}$ $\displaystyle {\frac{{x-u_j}}{{u_i-u_j}}}$ (28)

with the property that

Li(uj) = $\displaystyle \left\{\vphantom{ \begin{array}{rcl} 0 & {\rm if} i \neq j \\  1 & {\rm otherwise} & \end{array} }\right.$$\displaystyle \begin{array}{rcl} 0 & {\rm if} i \neq j \\  1 & {\rm otherwise} & \end{array}$ (29)

Proposition 5   Let v0,..., vn-1 be in $ \bf k$. There is a unique polynomial f $ \in$ $ \bf k$[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  =  $\displaystyle \Sigma_{{{0 \leq i < n}}}^{{}}$ 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 hence is the zero polynomial. $ \qedsymbol$

Proposition 6   Evaluating a polynomial f $ \in$ $ \bf k$[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 $ \cal {O}$(n2) operations in $ \bf k$.

Proof. We saw in Remark 7 that evaluating the polynomial f of degree n at one point costs 2n - 2 operations in $ \bf k$. 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 $ \cal {O}$(n2) operations in $ \bf k$. 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)  =  $\displaystyle {\frac{{q_i}}{{q_i(u_i)}}}$ (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 leading to i - 1. Hence computing p2,..., pn = m amounts to

$\displaystyle \Sigma_{{{2 \leq i \leq n}}}^{{}}$ 2 i - 1 = $\displaystyle \Sigma_{{{1 \leq i \leq n-1}}}^{{}}$ 2 i + 1
  = 2$\displaystyle \Sigma_{{{1 \leq i \leq n-1}}}^{{}}$i  +  n - 1
  = 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 $ \bf k$. 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 $ \bf k$ (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

amounting to n2 - n. Finally the total cost is 6n2 - 2n - 1 + 2 n2 - n = 8 n2 - 3 n - 1 $ \qedsymbol$

Remark 8   We consider the map

E : $\displaystyle \begin{array}{lll} {\bf k}^n & \rightarrow & {\bf k}^n \\  (f_0, ...
...eq j < n} f_j u_0^j, \ldots, {\Sigma}_{0 \leq j < n} f_j u_{n-1}^j) \end{array}$ (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 $ \bf k$-linear and it can be represented by the Vandermonde matrix

VDM(u0,..., un-1)  =  $\displaystyle \left(\vphantom{ \begin{array}{lllll} 1 & u_0 & u_0^2 & \cdots & ...
...s \\  1 & u_{n-1} & u_{n-1}^2 & \cdots & u_{n-1}^{n-1} \\  \end{array} }\right.$$\displaystyle \begin{array}{lllll} 1 & u_0 & u_0^2 & \cdots & u_0^{n-1} \\  1 &...
...& & \vdots \\  1 & u_{n-1} & u_{n-1}^2 & \cdots & u_{n-1}^{n-1} \\  \end{array}$$\displaystyle \left.\vphantom{ \begin{array}{lllll} 1 & u_0 & u_0^2 & \cdots & ...
...s \\  1 & u_{n-1} & u_{n-1}^2 & \cdots & u_{n-1}^{n-1} \\  \end{array} }\right)$ (35)

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


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