Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleApproximate computation of zero-dimensional polynomial ideals
Author(s) Daniel Heldt, Martin Kreuzer, Sebastian Pokutta, Hennie Poulisse
TypeArticle in Journal
AbstractThe Buchberger–Möller 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 Gröbner 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.
KeywordsBuchberger–Möller algorithm, Ideal membership, Border basis
URL http://www.sciencedirect.com/science/article/pii/S0747717109000935
JournalJournal of Symbolic Computation
Pages1566 - 1591
NoteIn Memoriam Karin Gatermann
Translation No
Refereed No