Computing Grobner Bases for Vanishing Ideals of Finite Sets of Points

Jeff Farr (CECM)

We present an algorithm that incrementally computes a Grobner basis for
the vanishing ideal of any finite set of points in an affine space under
any monomial order, and we apply this algorithm to polynomial
interpolation in multiple variables.  For the case of distinct points, the
algorithm is a natural generalization of Newton's interpolation for
univariate polynomials. The time complexity in the worst case is
exponential in term of the number of variables. Computational evidence
suggests, however, that it compares favorably with two known algorithms
when the number of variables is small relative to the number of points. We
also present a preprocessing technique that significantly enhances the
performance of all the algorithms considered.