System of polynomial equations

For the case of solutions of which all components are integers or rational numbers, see Diophantine equation.

A simple example of a system of polynomial equations is Its solutions are the four pairs (x, y) = (1, 2), (2, 1), (-1, -2), (-2, -1).

The subject of this article is the study of generalizations of such an examples, and the description of the methods that are used for computing the solutions.

The solutions are sought in the complex numbers, or more generally in an algebraically closed field containing the coefficients.

Searching for the real or rational solutions are much more difficult problems that are not considered in this article.

The Barth surface, shown in the figure is the geometric representation of the solutions of a polynomial system reduced to a single equation of degree 6 in 3 variables.

By Hilbert's Nullstellensatz this means that 1 is a linear combination (with polynomials as coefficients) of the first members of the equations.

For example, the system x3 – 1 = 0, x2 – 1 = 0 is overdetermined (having two equations but only one unknown), but it is not inconsistent since it has the solution x = 1.

This is a non-trivial result of commutative algebra that involves, in particular, Hilbert's Nullstellensatz and Krull's principal ideal theorem.

[3] Bézout's theorem asserts that a well-behaved system whose equations have degrees d1, ..., dn has at most d1⋅⋅⋅dn solutions.

This exponential behavior makes solving polynomial systems difficult and explains why there are few solvers that are able to automatically solve systems with Bézout's bound higher than, say, 25 (three equations of degree 3 or five equations of degree 2 are beyond this bound).

[citation needed] The first thing to do for solving a polynomial system is to decide whether it is inconsistent, zero-dimensional or positive dimensional.

For this test, the best monomial order (that is the one which leads generally to the fastest computation) is usually the graded reverse lexicographic one (grevlex).

In fact there are many different "relevant properties", which involve almost every subfield of algebraic geometry.

The classical algorithm for solving these question is cylindrical algebraic decomposition, which has a doubly exponential computational complexity and therefore cannot be used in practice, except for very small examples.

In the case of this simple example, it may be unclear whether the system is, or not, easier to solve than the equation.

The definition of regular chains implies that the univariate equation obtained from fi has degree di and thus that the system has d1 ... dn solutions, provided that there is no multiple root in this resolution process (fundamental theorem of algebra).

Every zero-dimensional system of polynomial equations is equivalent (i.e. has the same solutions) to a finite number of regular chains.

It consists in computing first the Gröbner basis for the graded reverse lexicographic order (grevlex), then deducing the lexicographical Gröbner basis by FGLM algorithm[5] and finally applying the Lextriangular algorithm.

[9] The second issue is generally solved by outputting regular chains of a special form, sometimes called shape lemma, for which all di but the first one are equal to 1.

[10] A RUR of a zero-dimensional system consists in a linear combination x0 of the variables, called separating variable, and a system of equations[11] where h is a univariate polynomial in x0 of degree D and g0, ..., gn are univariate polynomials in x0 of degree less than D. Given a zero-dimensional polynomial system over the rational numbers, the RUR has the following properties.

The RUR shares with equiprojectable decomposition the property of producing an output with coefficients of relatively small size.

For zero-dimensional systems, the RUR allows retrieval of the numeric values of the solutions by solving a single univariate polynomial and substituting them in rational functions.

In practice, this provides an output with much smaller coefficients, especially in the case of systems with high multiplicities.

To deduce the numeric values of the solutions from a RUR seems easy: it suffices to compute the roots of the univariate polynomial and to substitute them in the other equations.

There are at least four software packages which can solve zero-dimensional systems automatically (by automatically, one means that no human intervention is needed between input and output, and thus that no knowledge of the method by the user is needed).

Internally, this solver, designed by F. Rouillier computes first a Gröbner basis and then a Rational Univariate Representation from which the required approximation of the solutions are deduced.

The rational univariate representation may be computed with Maple function Groebner[RationalUnivariateRepresentation].

This solver computes the isolated complex solutions of polynomial systems having as many equations as variables.

The fourth solver is the Maple library RegularChains, written by Marc Moreno-Maza and collaborators.