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

From MaRDI portal
Revision as of 10:20, 11 July 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Almost vanishing polynomials for sets of limited precision points
scientific article

    Statements

    Almost vanishing polynomials for sets of limited precision points (English)
    0 references
    0 references
    6 November 2009
    0 references
    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}.
    0 references
    vanishing ideal
    0 references
    border bases
    0 references
    Gröbner bases
    0 references
    limited precision data
    0 references
    stable order ideal
    0 references
    \texttt{CoCoA}
    0 references
    approximate vanishing ideal
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references