Almost vanishing polynomials for sets of limited precision points (Q1034545)

Given a set \(\mathbb{X}\) of \(s\) points in \(\mathbb{R}^n\) whose coordinates are known only with limited precision \(\epsilon\), each `admissible perturbation' \({\tilde{\mathbb{X}}}\) of \(s\) points whose coordinates differ from those of the original set by less than the specified precision are possible candidates for the `true' set of points. Thus there are multiple possibilities for specifying a set of polynomials to describe \(\mathbb{X}\), depending upon one's goals. In this paper, the author presents an algorithm which produces a set of polynomials \(\mathcal{J}\), with support \(\mathcal{O}\), that describes \(\mathbb{X}\) and all of its admissible perturbations in the sense that the polynomials are `almost vanishing', w.r.t. the norm of their coefficient vectors, at the original set of points and each of its admissible perturbations. Additionally, if there is a `nice' geometrical structure upon which all of the points of some admissible perturbation lie, it is \textit{possible} (though not guaranteed) that the algorithm will find the polynomial(s) describing the structure. The algorithm, appropriately named the ``numerical Buchberger-Möller (NBM) algorithm'', is based on Buchberger and Möller's algorithm [\textit{H.M. Möller} and \textit{B. Buchberger}, in: Computer algebra, EUROCAM '82, Conf. Marseille/France 1982, Lect. Notes Comput. Sci. 144, 24--31 (1982; Zbl 0549.68026)] which, given a term order \(\sigma\), computes the \(\sigma\)-Gröbner basis GB of the vanishing ideal of \(\mathbb{X}\). The NBM algorithm is appropriately modified to handle approximate data: A key requirement of the Buchberger/Möller algorithm is the ability to assert the linear independence of power products evaluated at a set of points. The NBM algorithm accomplishes this in the presence of limited precision by using ``the sensitivity of the least squares problem''. The modified algorithm does not, in general, produce a Gröbner basis of the vanishing ideal of \(\mathbb{X}\). However, the author gives several examples where it produces `approximately vanishing' polynomials describing the geometric structure(s) from which the test points were perturbed. The algorithm has been implemented in the \texttt{CoCoALib} (\texttt{CoCoA} release 4.7, available at \url{http://apcocoa.org}) under the name \texttt{StableBBasisNBM5}.