Home Online Manual
Top
Back: fareypoly
Forward: BerlekampMassey
FastBack:
FastForward:
Up: ffmodstd_lib
Top: Singular Manual
Contents: Table of Contents
Index: Index
About: About this document

D.15.9.2 polyInterpolation

Procedure from library ffmodstd.lib (see ffmodstd_lib).

Usage:
polyInterpolation(d, e[, n, L]); d list, e list, n int, L list

Return:
a list l_p where f:=l_p[1] is a polynomial of degree at most size(d)-1 which satisfies the conditions f(d[i])=e[i] for all i, l_p[2] is the product of all (var(n)-d[i]) for 1 <= i <= size(d) and l_p[3]=d.

Note:
The procedure applies the Newton interpolation algorithm to the pair (d,e) and returns the output w.r.t. the first variable (default) of the ground ring. If an optional parameter n, 1<=n<=N (N is the number of variables in the current basering), is given, then the procedure returns the list l_p w.r.t. the n-th variable. Moreover, if the number of points (d'[i],e'[i]) is not large enough to obtain the target polynomial, L = polyInterpolation(d', e', n) can be provided as an optional parameter to add more interpolation points. The elements in the first list must be distinct.

Example:
 
LIB "ffmodstd.lib";
ring rr=23,(x,y),dp;
list d = 1,2,3,4;
list e = -1,10,3,8;
polyInterpolation(d,e);
==> [1]:
==>    5x3+7x2+x+9
==> [2]:
==>    x4-10x3-11x2-4x+1
==> [3]:
==>    [1]:
==>       1
==>    [2]:
==>       2
==>    [3]:
==>       3
==>    [4]:
==>       4
polyInterpolation(d,e,2)[1];
==> 5y3+7y2+y+9
list d1 = 5,6;
list e1 = -7,6;
list L = polyInterpolation(d,e);
L = polyInterpolation(d1,e1,1,L); // add points
L;
==> [1]:
==>    10x5-5x4+3x3+3x2-x-11
==> [2]:
==>    x6+2x5-9x4+x3-9x2+7x+7
==> [3]:
==>    [1]:
==>       1
==>    [2]:
==>       2
==>    [3]:
==>       3
==>    [4]:
==>       4
==>    [5]:
==>       5
==>    [6]:
==>       6
ring R = (499,a),x,dp;
list d2 = 2,3a,5;
list e2 = (a-2), (9a2-8a), (a+10);
polyInterpolation(d2,e2);
==> [1]:
==>    x2-3*x+(a)
==> [2]:
==>    x3+(-3a-7)*x2+(21a+10)*x+(-30a)
==> [3]:
==>    [1]:
==>       2
==>    [2]:
==> (3a)
==>    [3]:
==>       5