Certification for polynomial systems via square subsystems
Given a set of polynomials \(f = (f_1,\dots,f_N)\) with \(f_i \in \mathbb C[z_1,\dots,z_n]\), an approximate solution to the system \(f_1(z) = 0, \dots, f_N(z) = 0\) is an estimate \(\hat \zeta\) of some point \(\zeta\) in the common vanishing locus of the \(f_i\) (i.e. \(\zeta\) is a solution of the system \(f\)). By ``approximate solution the authors mean that the approximation error \(\| \zeta - \hat \zeta \|\) can be refined efficiently as a function of the input size and the desired precision. To verify that an approximation is suitable, numerical certification seeks to develop criteria and algorithms. In this paper the authors produce algorithms to address the following problems: \begin{itemize} \item[(1)] How to certify that a point \(\zeta \in \mathbb C^n\) is an approximate solution of \(f\)? \item[(2)] If it is known that \(f\) has \(e\) solutions, how can we certify that a set \(Z \subset \mathbb C^n\) of \(e\) points consists of approximate solutions to \(f\)? \end{itemize} The authors consider numerical certification of approximate solutions to a system of polynomial equations with more equations than unknowns by first certifying solutions to a suitable square subsystem. They give several approaches, using different additional information. Among these are liaison, Newton-Okounkov bodies, or intersection theory. They may be used to certify individual solutions, reject non-solutions, or certify that we have found all solutions.
- Certifying solutions to overdetermined and singular polynomial systems over \(\mathbb{Q}\)
- Certifying simple zeros of over-determined polynomial systems
- A heuristic method for certifying isolated zeros of polynomial systems
- Effective certification of approximate solutions to systems of equations involving analytic functions
- Algorithm 921: alphaCertified: certifying solutions to polynomial systems
- A lifted square formulation for certifiable Schubert calculus
- A primal-dual formulation for certifiable computations in Schubert calculus
- A short survey on Kantorovich-like theorems for Newton's method
- Algorithm 921: alphaCertified: certifying solutions to polynomial systems
- Certifying solutions to overdetermined and singular polynomial systems over \(\mathbb{Q}\)
- Complexity of Bezout's Theorem I: Geometric Aspects
- Effective certification of approximate solutions to systems of equations involving analytic functions
- Enumerative geometry for the real Grassmannian of lines in projective space
- Gorenstein liaison, complete intersection liaison invariants and unobstructedness
- scientific article; zbMATH DE number 4132298 (Why is no real title available?)
- scientific article; zbMATH DE number 1001729 (Why is no real title available?)
- scientific article; zbMATH DE number 3760758 (Why is no real title available?)
- scientific article; zbMATH DE number 3766957 (Why is no real title available?)
- scientific article; zbMATH DE number 3514184 (Why is no real title available?)
- scientific article; zbMATH DE number 3992817 (Why is no real title available?)
- scientific article; zbMATH DE number 3451984 (Why is no real title available?)
- scientific article; zbMATH DE number 835749 (Why is no real title available?)
- scientific article; zbMATH DE number 4196114 (Why is no real title available?)
- Introduction to Interval Analysis
- Khovanskii bases, higher rank valuations, and tropical geometry
- Mixed volume and an extension of intersection theory of divisors
- Newton methods for nonlinear problems. Affine invariance and adaptive algorithms.
- Newton's method for overdetermined systems of equations
- Newton-Algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken
- Newton-Okounkov bodies, semigroups of integral points, graded algebras and intersection theory
- Numerical algebraic geometry
- Numerical Schubert calculus via the Littlewood-Richardson homotopy algorithm
- Optimal Error Bounds for the Newton–Kantorovich Theorem
- Safe Starting Regions for Iterative Methods
- Solving zero-dimensional systems through the rational univariate representation
- The Kantorovich Theorem for Newton's Method
- The number of roots of a system of equations
- The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
- Using Gröbner bases to determine algebra membership, split surjective algebra homomorphisms determine birational equivalence
- Using SAGBI bases to compute invariants
- Validated numerics. A short introduction to rigorous computations.
- Certifying simple zeros of over-determined polynomial systems
- On the equations defining some Hilbert schemes
- Certifying solutions to overdetermined and singular polynomial systems over \(\mathbb{Q}\)
- Certifying polynomials for AC^0(parity) circuits, with applications
- Certification Using Newton-Invariant Subspaces
- Certifying solutions to square systems of polynomial-exponential equations
- Effective certification of approximate solutions to systems of equations involving analytic functions
- Certifying approximate solutions to polynomial systems on Macaulay2
- Numerical homotopies from Khovanskii bases
- Newton-Okounkov bodies of chemical reaction systems
- \texttt{SubalgebraBases} in Macaulay2
Uses Software
This page was built for publication: Certification for polynomial systems via square subsystems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q820969)
