Approximate computation of zero-dimensional polynomial ideals (Q731932): Difference between revisions

\textit{B. Buchberger} and \textit{H. M. Möller} developed an algorithm to compute the vanishing ideal of a finite set of points [Lect. Notes Comput. Sci. 144, 24--31 (1982; Zbl 0549.68026)]. The corresponding Gröbner basis is numerical unstable. The aim of the paper is to introduce a numerically stable so-called Approximate Vanishing Ideal Algorithm which computes a set of polynomials that almost vanish at the given points and almost form a border basis. Singular value decomposition is used to adapt the Buchberger--Möller algorithm to the approximate setting. A modification of the algorithm is given which computes a Macaulay basis of an approximate vanishing ideal. The Border Basis Algorithm [\textit{A. Kehrein} and \textit{M. Kreuzer}, J. Pure Appl. Algebra 205, No. 2, 279--295 (2006; Zbl 1097.13036)] is also generalized to the approximate setting. The approximate membership problem for zero--dimensional ideals is studied.