Incomplete Gröbner basis as a preconditioner for polynomial systems (Q1008653)

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.