An algorithm for implicit interpolation

作者：Gimenez Nardo^*

来源：Applicable Algebra in Engineering Communication and Computing, 2014, 25(1-2): 119-157.

DOI：10.1007/s00200-014-0213-8

• Multivariate polynomial interpolation
• Zero dimensional polynomial ideals
• Geometric solutions
• Trace theory

We study the multivariate polynomial interpolation problem when the set of nodes is a zero-dimensional affine variety given as the set of zeros of polynomials with integer coefficients that generate a radical ideal. We describe a symbolic procedure to construct, from , a basis of a space of interpolants for , where is the number of nodes. This construction yields a space of interpolants which is uniquely determined by the sequence and such that the degree of the interpolants is at most , where is an upper bound for the degrees of . Furthermore, we exhibit a probabilistic algorithm that, from and a given additional polynomial , computes the polynomials and the interpolant of with roughly bit operations. Here is the cost of evaluation of and the degree of the input system an upper bound for the heights of the polynomials the height of the degree of , and the height of . The numbers and are always bounded by and respectively and in certain cases of practical interest these numbers are considerably smaller than these bounds.

• 出版日期2014-4