Computing Grobner Bases for Vanishing Ideals of Finite Sets of Points
Jeff Farr (CECM)Monday January 26, 2004, in K9509 at 3:30pm.
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.