Incomplete Gröbner basis as a preconditioner for polynomial systems
Bézout numberdeficient nonlinear algebraic systemdegree reductionhomotopy continuationincomplete Gröbner basis (IGB)PHCpackpreconditionerS-polynomialssubtraction polynomialtruncated Gröbner basis
Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Real polynomials: location of zeros (26C10) Numerical computation of solutions to systems of equations (65H10) Global methods, including homotopy approaches to the numerical solution of nonlinear equations (65H20)
The particular polynomials chosen to represent a nonlinear algebraic system can have a large impact on the ease or difficulty of finding its solution(s). As a result, various methods of preconditioning systems have been proposed. In this paper, a particular method of limited Gröbner basis calculation is used to replace the original polynomials of a deficient system with some that give a system with the same finite solutions, but of smaller total degree. The resulting system can thus be solved faster. Let \(R = k[x_1,\dots,x_n]\) be a polynomial ring, \(k\) the field of real numbers. Suppose \(F = \{p_1,\dots,p_m\} \subset R\) is a system of polynomials defining the nonlinear algebraic system to be solved, and let \(d\) be the maximum degree of the \(p_i\)'s. Assume the monomial ordering is the graded lexicographic order. The authors define an incomplete Gröbner basis (IGB) to be one for which only the S-polynomials of degree at most \(d\) are considered (and reduced). Note that this is not quite the same as (the most common definition of) a \(d\)-truncated Gröbner basis, wherein only S-pairs of degree at most \(d\) are considered. In particular, the former may compute more pairs than the latter. Additionally, note that there is no requirement that the polynomials be homogeneous. The authors note that a reduced IGB may have more solutions than the original system, but that the extra solutions must have at least one coordinate equal to zero, and they can be eliminated through testing. Further, the authors point out that by limiting the computation in this manner, the IGB can be computed in polynomial time. The paper concludes with numerous examples of the efficacy of this approach to preconditioning in reducing the total degree, multi-homogeneous Bezout number, general linear-product Bézout number and mixed volume of various systems to be solved by homotopy continuation. For comparison, the same measures are listed for systems preconditioned with PHCpack.
- A new start system for solving deficient polynomial systems using continuation
- Algorithm 795
- Bézout number calculations for multi-homogeneous polynomial systems
- Coefficient-parameter polynomial continuation
- Finding all isolated solutions to polynomial systems using HOMPACK
- Finding all isolated zeros of polynomial systems in \(\mathbb{C}^n\) via stable mixed volumes
- scientific article; zbMATH DE number 3937298 (Why is no real title available?)
- scientific article; zbMATH DE number 50337 (Why is no real title available?)
- scientific article; zbMATH DE number 1069614 (Why is no real title available?)
- scientific article; zbMATH DE number 967945 (Why is no real title available?)
- Mathematical reduction of a heart dipole model
- Minimizing multi-homogeneous Bézout numbers by a local search method
- Nonlinear reduction for solving deficient polynomial systems by continuation methods
- The membership problem for unmixed polynomial ideals is solvable in single exponential time
- Why you cannot even hope to use Gröbner bases in public key cryptography: An open letter to a scientist who failed and a challenge to those who have not yet failed
This page was built for publication: Incomplete Gröbner basis as a preconditioner for polynomial systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1008653)
