Incomplete Gröbner basis as a preconditioner for polynomial systems
type: Item
instance of: scholarly article
title: Incomplete Gröbner basis as a preconditioner for polynomial systems
zbMATH Open document ID: 1165.65026
author: Yang Sun
author: Yu-Hui Tao
author: Fengshan Bai
published in: Journal of Computational and Applied Mathematics
publication date: 2009-03-30T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 65H10
Mathematics Subject Classification ID: 65H20
Mathematics Subject Classification ID: 13P10
Mathematics Subject Classification ID: 26C10
zbMATH DE Number: 5534906
zbMATH Keywords: incomplete Gröbner basis (IGB)
zbMATH Keywords: homotopy continuation
zbMATH Keywords: preconditioner
zbMATH Keywords: PHCpack
zbMATH Keywords: truncated Gröbner basis
zbMATH Keywords: deficient nonlinear algebraic system
zbMATH Keywords: degree reduction
zbMATH Keywords: Bézout number
zbMATH Keywords: S-polynomials
zbMATH Keywords: subtraction polynomial
reviewed by: Alyson Reeves
describes a project that uses: PoSSo
describes a project that uses: PHCpack
MaRDI profile type: Publication
full work available at URL: j.cam.2008.05.054
OpenAlex ID: W2091193233
cites work: 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
cites work: Q5690494
cites work: The membership problem for unmixed polynomial ideals is solvable in single exponential time
cites work: Finding all isolated zeros of polynomial systems in \(\mathbb{C}^n\) via stable mixed volumes
cites work: Q3710617
cites work: Minimizing multi-homogeneous Bézout numbers by a local search method
cites work: Q4356576
cites work: Q4000024
cites work: Coefficient-parameter polynomial continuation
cites work: Finding all isolated solutions to polynomial systems using HOMPACK
cites work: Mathematical reduction of a heart dipole model
cites work: A new start system for solving deficient polynomial systems using continuation
cites work: Nonlinear reduction for solving deficient polynomial systems by continuation methods
cites work: Algorithm 795
cites work: Bézout number calculations for multi-homogeneous polynomial systems
DOI: 10.1016/J.CAM.2008.05.054
description: scientific article; zbMATH DE number 5534906