# Singular

#### D.15.12.4 sparseInterpolation

Procedure from library `ffmodstd.lib` (see ffmodstd_lib).

Usage:
sparseInterpolation(Br, La, lpr, n[, m]); Br poly, La list, lpr list, n int, m int

Return:
a polynomial B in the polynomial ring Q[var(n+1),...,var(n+size(lpr))] satisfying the relation La[i] = B(lpr[1]^i,...,lpr[size(lpr)]^i).

Note:
The polynomial Br in Q[var(n)] is the minimal polynomial obtained by applying the SINGULAR command BerlekampMassey to the sequence (La[j]), 1<=j<=size(La). By default the exponent i starts from 1. However, if the optional parameter m>=0 is provided, then it starts from m.
The list lpr must be a list of distinct primes.

Example:
 ```LIB "ffmodstd.lib"; ring rr=0,(x,y),dp; list lpr = 2,3; // assign 2 for x and 3 for y list La = 150,3204,79272,2245968,70411680, 2352815424, 81496927872; // La[i] = number(subst(f,y,lpr[1]^i,z,lpr[2]^i)); for f = x2y2+2x2y+5xy2 and i=1,...,7 poly Br = BerlekampMassey(La,1)[1]; Br; ==> x3-66x2+1296x-7776 sparseInterpolation(Br,La,lpr,0); // reconstruct f default ==> x2y2+2x2y+5xy2 La = 97,275,793,2315,6817; // La[i] = number(subst(g,y,lpr[1]^i,z,lpr[2]^i)); for g = x+y and i=4,...,8 Br = BerlekampMassey(La,1)[1]; Br; ==> x2-5x+6 sparseInterpolation(Br,La,lpr,0,4); ==> x+y ```