Almost vanishing polynomials for sets of limited precision points (Q1034545): Difference between revisions
From MaRDI portal
Changed an Item |
Normalize DOI. |
||
(7 intermediate revisions by 5 users not shown) | |||
Property / DOI | |||
Property / DOI: 10.1016/j.jsc.2009.06.002 / rank | |||
Property / describes a project that uses | |||
Property / describes a project that uses: CoCoA / rank | |||
Normal rank | |||
Property / describes a project that uses | |||
Property / describes a project that uses: CoCoALib / rank | |||
Normal rank | |||
Property / describes a project that uses | |||
Property / describes a project that uses: ApCoCoA / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2017337676 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 0807.3412 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Thinning out redundant empirical data / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Stable border bases for ideals of points / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3341887 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Approximate computation of zero-dimensional polynomial ideals / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4325914 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4507801 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5317677 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Approximate varieties, approximate ideals and dimension reduction / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Floating point Gröbner bases. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3156429 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Numerical Polynomial Algebra / rank | |||
Normal rank | |||
Property / DOI | |||
Property / DOI: 10.1016/J.JSC.2009.06.002 / rank | |||
Normal rank |
Latest revision as of 14:09, 10 December 2024
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
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