Approximate computation of zero-dimensional polynomial ideals
The Buchberger-Moller algorithm is a well-known efficient tool for Computing the vanishing ideal of a finite set of points. if the coordinates of the points are (imprecise) measured data, the resulting Grobner basis is numerically unstable. In this paper we introduce a numerically stable Approximate Vanishing Ideal (AVI) Algorithm which computes a set of polynomials that almost vanish at the given points and almost form a border basis. Moreover, we provide a modification of this algorithm which produces a Macaulay basis of an approximate vanishing ideal. We also generalize the Border Basis Algorithm ([Kehrein, A., Kreuzer, M., 2006. Computing border bases. J. Pure Appl. Algebra 205,279-295]) to the approximate setting and study the approximate membership problem for zero-dimensional polynomial ideals. The algorithms are then applied to actual industrial problems. (C) 2009 Elsevier Ltd. All rights reserved.
buchberger-moller algorithm border basis ideal membership