Complex Polynomial Systems
Introduction
The
Mathematica functions
Reduce,
Resolve, and
FindInstance allow you to solve a wide variety of problems that can be expressed in terms of equations and inequalities. The functions use a collection of algorithms applicable to classes of problems satisfying particular properties, as well as a set of heuristics that attempt to reduce the given problem to a sequence of problems that can be solved using the algorithms. This tutorial describes the algorithms used to solve the class of problems known as complex polynomial systems. It characterizes the structure of the returned answers and describes the options that affect various aspects of the methods involved.
A complex polynomial system is an expression constructed with polynomial equations and inequations
combined using logical connectives and quantifiers
An occurrence of a variable
inside
or
is called a bound occurrence, and any other occurrence of
is called a free occurrence. A variable
is called a free variable of a complex polynomial system if the system contains a free occurrence of
. A complex polynomial system is quantifier-free if it contains no quantifiers.
Here is an example of a complex polynomial system with free variables
,
, and
.
In
Mathematica, quantifiers are represented using the functions
Exists (
) and
ForAll (
).
Any complex polynomial system can be transformed to the prenex normal form
where each
is a quantifier
or
, and
is quantifier-free.
Any quantifier-free complex polynomial system can be transformed to the disjunctive normal form
where each
is a polynomial equation or inequation.
Reduce,
Resolve, and
FindInstance always put complex polynomial systems in the prenex normal form, with quantifier-free parts in the disjunctive normal form, and subtract the sides of the equations and inequations to put them in the form
In all the tutorials for complex polynomial system solving, assume that the system has been transformed to this form.
Reduce can solve arbitrary complex polynomial systems. The solution (possibly after expanding
with respect to
) is a disjunction of terms of the form
where
are the free variables of the system, each
is a polynomial, each
is an algebraic function expressed using radicals or
Root objects, and any terms of the conjunction (
2) may be absent. Each
is well defined, that is, no denominators or leading terms of
Root objects in
become zero for any
satisfying the preceding terms of the conjunction (
2).
This solves the system (
1).
| Out[1]= |  |
Resolve can eliminate quantifiers from arbitrary complex polynomial systems. If no variables are specified, the result is a logical combination of terms
where
and
are polynomials, and each
is a free variable of the system. With variables specified in the input,
Resolve gives the same answer as
Reduce.
This eliminates quantifiers from the system (
1).
| Out[2]= |  |
FindInstance can handle arbitrary complex polynomial systems giving instances of complex solutions, or an empty list for systems that have no solutions. If the number of instances requested is more than one, the instances are randomly generated from the full solution of the system, and therefore they may depend on the value of the
option. If one instance is requested, a faster algorithm that produces one instance is used, and the instance returned is always the same.
This finds a solution for the system (
1).
| Out[3]= |  |
The main tool used in solving complex polynomial systems is the Gröbner basis algorithm [
1], which is available in
Mathematica as the
GroebnerBasis function.
Gröbner Bases
Theory
This section gives a very brief introduction to the theory of Gröbner bases. It presents only the properties that are necessary to describe the algorithms used by
Mathematica in solving complex polynomial systems. For a more complete presentation see, for example, [
1,
2]. Note that what [
2] calls a monomial, [
1] calls a term, and vice versa. This tutorial uses the terminology of [
1].
A monomial in
is an expression of the form
with non-negative integers
.
Let
be the set of all monomials in
. A monomial order is a linear order
on
, such that
for all
, and
implies
for all
.
Let
be a field, the domain of integers, or the domain of univariate polynomials over a field. Let
and
be functions
defined as follows. If
is a field,
, and
. If
is the domain of integers,
and
are the integer quotient and remainder functions, with
. If
is the domain of univariate polynomials over a field,
and
are the polynomial quotient and remainder functions.
A product
, where
is a nonzero element of
and
is a monomial, is called a term.
Let
be a monomial order on
, and let
. The leading monomial
of
is the
-largest monomial appearing in
, the leading coefficient
of
is the coefficient at
in
, and the leading term
of
is the product
.
A Gröbner basis of an ideal
in
, with respect to a monomial order
, is a finite set
of polynomials, such that for each
, there exists
, such that
divides
. Every ideal
has a Gröbner basis (see [
1] for a proof).
Let
, and let
be a monomial. A term
is reducible modulo
, if
divides
, and
. If
is reducible modulo
, the reduction of
modulo
is the polynomial
Note that if
, then
; otherwise,
.
Let
, and let
be an ordered finite subset of
.
is reducible modulo
if
contains a term reducible modulo an element of
. The reduction
of
modulo
is defined by the following procedure. While the set
of terms of
reducible modulo an element of
is not empty, take the term
with the
-largest monomial, take the first
, such that
is reducible modulo
, and replace the term
in
with
. Note that the monomials of terms
chosen in subsequent steps of the procedure form a
-descending chain, and each monomial can appear at most
times, where
is the number of elements of
, hence the procedure terminates.
A Gröbner basis
is semi-reduced if for all
,
is not reducible modulo
, and if
is the domain of integers,
.
The
Mathematica function
GroebnerBasis returns semi-reduced Gröbner bases. In the following discussion, all Gröbner bases are assumed to be semi-reduced. Note that this is not the same as reduced Gröbner bases defined in the literature, since here the basis polynomials are not required to be monic. For a fixed monomial order, every ideal has a unique reduced Gröbner basis. Semi-reduced Gröbner bases defined here are only unique up to multiplication by invertible elements of
(see
Property 2).
Property 1: Let
be a Gröbner basis of an ideal
in
, and let
. Then
iff
.
This is a simple consequence of the definitions.
Property 2: Let
and
be two Gröbner bases of an ideal
with respect to the same monomial order
, and suppose that elements of
and
are ordered by their leading monomials. Then
, and for all
, if
is the domain of integers,
; otherwise,
for some invertible element
of
.
Proof: If
, then
is reducible modulo
or
is reducible modulo
. Hence the leading monomials of the elements of a Gröbner basis are all different. Without loss of generality, assume
. For induction, fix
and suppose that for all
,
for some invertible element
of
. If
is the domain of integers,
. Without loss of generality, assume
. Since
belongs to
, there exists
such that
divides
. Then
, and so
. If
, then
would be reducible modulo
and also modulo
, which is impossible, since
is semi-reduced. Hence
, and
, and
divides
. Similarly,
divides
. Therefore, there exists an invertible element
of
, such that
. If
is the domain of integers,
and
are positive, and so
. Let
. Suppose
. Since
belongs to
,
must be divisible by
, for some
. Let
and
be the coefficients at
in
and
. If
is a field, the term
of
is reducible modulo
, which contradicts the assumption that
is semi-reduced. If
is the domain of univariate polynomials over a field,
and so either
is reducible modulo
, or
is reducible modulo
, which contradicts the assumption that
and
are semi-reduced. Finally, let
be the domain of integers. Since neither
is reducible modulo
nor
is reducible modulo
,
and
. Hence
, which is impossible, since
is divisible by
. Therefore
, and so
. By induction on
, for all
,
. If
, then
would be reducible modulo some
, with
, and hence
would be reducible modulo
. Therefore
, which completes the proof of
Property 2.Property 3: Let
be an ideal in
, let
, and let
be a Gröbner basis of the ideal
in
. Then
belongs to the radical of
iff
for an invertible element
of
.
If an ideal contains invertible elements of
,
GroebnerBasis always returns
.
belongs to the ideal
for any non-negative integer
. Hence, if
belongs to the radical of
, then 1 belongs to
. Since
is a Gröbner basis of
, it must contain an element
whose leading coefficient divides 1. Hence
is an invertible element of
. Since
is semi-reduced and
divides any term,
. Now suppose that
for an invertible element
of
. Then 1 belongs to
, and so
where each
belongs to
, and each
belongs to
. Hence comparing coefficients at powers of
leads to the following equations modulo
:
,
, for
, and
. Then,
, for
, and
modulo
. Therefore,
belongs to the radical of
, which completes the proof of
Property 3.
The following more technical property is important for solving complex polynomial systems.
Property 4: Let
be a Gröbner basis of an ideal
in
with a monomial order that makes monomials containing
greater than monomials not containing
, let
be the element of
with the lowest positive degree
in
, let
be the leading coefficient of
in
, and let
be all elements of
that do not depend on
. Then for any polynomial
and any point
if
,
, for
, and
, then
.
Proof: Consider the pseudoremainder
of the division of
by
as polynomials in
.
Since
and
belong to
, so does
. By
Property 1, reduction of
by
must yield zero. Since the degree of
in
is less than
,
cannot be reduced by any of the elements of
that depend on
. Hence
and so
. Since
, (
1) implies that
, which completes the proof of
Property 4.
Mathematica Function GroebnerBasis
The
Mathematica function
GroebnerBasis finds semi-reduced Gröbner bases. This section describes
GroebnerBasis options used in the solving of complex polynomial systems.
| | |
| CoefficientDomain | Automatic | the type of objects assumed to be coefficients |
| Method | Automatic | the method used to compute the basis |
| MonomialOrder | Lexicographic | the criterion used for ordering monomials |
GroebnerBasis options used in the solving of complex polynomial systems.
CoefficientDomain
This option specifies the domain
of coefficients. With the default
Automatic setting, the coefficient domain is the field generated by numeric coefficients present in the input.
| Integers | the domain of integers |
| InexactNumbers[prec] | inexact numbers with precision prec |
| Polynomials[x] | the domain of polynomials in  |
| RationalFunctions | the field of rational functions in variables not on the variable list given to GroebnerBasis |
| Rationals | the field of rational numbers |
Available settings for 
.
Note that the coefficient domain
also depends on the setting of the
Modulus option of
GroebnerBasis. With
Modulus->p, for a prime number
, the coefficient domain is the field
, or the field of rational functions over
if
.
Method
With the default setting
Method->Automatic,
GroebnerBasis normally uses a variant of the Buchberger algorithm. Another algorithm available is the Gröbner walk, which computes a Gröbner basis in an easier monomial order and then transforms it to the required harder monomial order. This is often faster than directly computing a Gröbner basis in the required order, especially if the input polynomials are known to be a Gröbner basis for the easier order. With the
Method->Automatic setting,
GroebnerBasis uses the Gröbner walk for the default
Rationals and
.
| GroebnerBasis[polys,vars,Method->{"GroebnerWalk","InitialMonomialOrder"->order1},MonomialOrder->order2] |
| find a Gröbner basis in  and use the Gröbner walk algorithm to transform it to a Gröbner basis in  |
Transforming Gröbner bases using the Gröbner walk algorithm.
MonomialOrder
This option specifies the monomial order. The value can be either one of the named monomial orders or a weight matrix. The following table gives conditions for
.
| Lexicographic |  |
| DegreeLexicographic |  |
| DegreeReverseLexicographic |  |
Monomial orders.
Quantifier elimination needs an order in which monomials containing quantifier variables are greater than monomials not containing quantifier variables. The
order satisfies this condition, but the following
usually leads to faster computations.
where
denotes total degree,
denotes free variables,
denotes quantifier variables,
and
are monomials, and
denotes the
order.
Using
requires the
GroebnerBasis syntax with elimination variables specified.
| GroebnerBasis[polys,xvars,yvars,MonomialOrder->EliminationOrder] |
| find a Gröbner basis in  |
Gröbner basis in elimination order.
By default,
GroebnerBasis with
drops the polynomials that contain
from the result, returning only basis polynomials in
. To get all basis polynomials, the value of the system option
from the
group must be changed. (
Mathematica changes the option locally in the quantifier elimination algorithm.) The option value can be changed with
| | |
| "EliminateFromGroebnerBasis" | True | whether GroebnerBasis with  should remove polynomials containing elimination variables |
System option 
.
This eliminates
from
. The answer is a polynomial whose zeros are the Zariski closure of the projection of the solution set of the two original equations on the
plane.
| Out[4]= |  |
The exact description of the projection of the solution set on the
plane depends on all basis polynomials. Note that the second basis polynomial cannot be zero if
or
is zero.
| Out[6]= |  |
This resets the system option to its default value.
Resolve gives the exact description of the projection of the solution set on the
plane.
| Out[8]= |  |
Decision Problems
A decision problem is a system with all variables existentially quantified, that is, a system of the form
where
are all variables in
. Solving a decision problem means deciding whether it is equivalent to
True or to
False, that is, deciding whether the quantifier-free system of polynomial equations and inequations
has solutions.
Solving this decision problem proves that a quadratic equation with a zero determinant cannot have two different roots.
| Out[9]= |  |
solving any decision problem can be reduced to solving a finite number of decision problems of the form
By Hilbert's Nullstellensatz and
Property 3 of Gröbner bases
has complex solutions iff
with an arbitrary monomial order, is different than
.
This shows that
has complex solutions.
| Out[10]= |  |
This shows that
has no complex solutions.
| Out[11]= |  |
When
Mathematica solves a decision problem, the monomial order used by the
GroebnerBasis computation is
, with
specified as the elimination variable list. This setting corresponds to the monomial ordering in which monomials containing
are greater than those that do not contain
, and the ordering of monomials not containing
is degree reverse lexicographic. If there is no inequation condition, there is no need to introduce
, and
Mathematica uses
.
Quantifier Elimination
For any complex polynomial system there exists an equivalent quantifier-free complex polynomial system. This follows from Chevalley's theorem, which states that a projection of a quasi-algebraically constructible set (a solution set of a quantifier-free system of polynomial equations and inequations) is a quasi-algebraically constructible set [
3]. Quantifier elimination is the procedure of finding a quantifier-free complex polynomial system equivalent to a given complex polynomial system. In
Mathematica, quantifier elimination for complex polynomial systems is done by
Resolve. It is also used by
Reduce and
FindInstance as the first step in solving or finding instances of solutions of complex polynomial systems.
Eliminating quantifiers from this system gives a condition for quadratic equations to have at least two different zeros.
| Out[12]= |  |
For complex polynomial systems
Mathematica uses the following quantifier elimination method. Given the identities
eliminating quantifiers from any complex polynomial system can be reduced to a finite number of single existential quantifier eliminations from systems of the form
To eliminate the quantifier from (
1),
Mathematica first computes the Gröbner basis of equations
with a monomial order that makes monomials containing
greater than monomials not containing
.
The monomial order used is
EliminationOrder, with
specified as the elimination variable list and
all basis polynomials kept.
If
contains no polynomials that depend on
, then a quantifier-free system equivalent to (
1) can be obtained by equating all elements of
to zero, and asserting that at least one coefficient of
as a polynomial in
is not equal to zero. Otherwise let
be the element of
with the lowest positive degree
in
, let
be the leading coefficient of
in
, and let
be all elements of
that do not depend on
. Now (
1) can be split into a disjunction of two systems
To eliminate the quantifier from (
2), the quantifier elimination procedure is called recursively. Since the ideal generated by
strictly contains the ideal generated by
, the Noetherian property of polynomial rings guarantees finiteness of the recursion.
If
belongs to the radical of the ideal generated by
, which is exactly when 1 belongs to
(
3) is equivalent to
False. Otherwise let
be the pseudoremainder of the division of
by
as polynomials in
. Then (
3) is equivalent to the quantifier-free system
To show that (
3) implies (
4), suppose that
satisfies (
3). Then
and there exists
, such that
Since
and
belong to the ideal generated by
,
and
. Hence
To show that (
4) implies (
3), suppose that
satisfies (
4). Then
Since
is a polynomial of degree
, and
is a nonzero polynomial of degree less than
, there is a root
of
such that
divides
but not
for some
. If
were zero, then
would divide
, which is impossible because it would imply that
divides
. Therefore
.
Property 4 shows that
for any polynomial
. Since
is a Gröbner basis of the ideal generated by
,
which completes the proof of correctness of the quantifier elimination algorithm.
This eliminates the quantifier from
. Here
,
, and
. Since
is a nonzero constant, (
2) is
False and the equivalent quantifier-free system is given by (
4). Since
is a nonzero constant, (
4) becomes
.
| Out[14]= |  |
This resets the system option to its default value.
Arbitrary Complex Polynomial Systems
FindInstance
FindInstance can handle arbitrary complex polynomial systems giving instances of complex solutions, or an empty list for systems that have no solutions. If the number of instances requested is more than one, the instances are randomly generated from the full solution of the system given by
Reduce. If one instance is requested, a faster algorithm that produces one instance is used. Here is a description of the algorithm used to find a single instance, or prove that a system has no solutions.
If the system contains general quantifiers (
), the
quantifier elimination algorithm is used to eliminate the innermost quantifiers until the system contains only existential quantifiers (
) or is quantifier-free. Note that
has solutions if and only if
has solutions, and if
is a solution of
, then
is a solution of (
1). Hence to find instances of solutions of systems containing only existential quantifiers it is enough to be able to find instances of quantifier-free systems. Moreover,
is a solution of
if and only if it is a solution of one of the
, with
, so it is enough to show how to find instances of solutions of
First compute the
GroebnerBasis 
of
with
, eliminating the polynomials that depend on
(if there is no inequation condition,
is the
GroebnerBasis of
with
). If
contains 1, there are no solutions. Otherwise, compute a subset
of
of the highest cardinality among subsets strongly independent modulo the ideal generated by
with respect to the degree reverse lexicographic order ([
1], Section 9.3). Reorder
so that
, and compute the lexicographic order
GroebnerBasis 
of the ideal generated by
. To compute
,
Mathematica uses the
Gröbner walk algorithm.
For each of the variables
,
, select the polynomial
with the smallest leading monomial among elements of
that depend on
and not on
. Let
be the leading coefficient of
as a polynomial in
. If
depends on a variable that is not in
, replace
with the lexicographic order Gröbner basis of the ideal generated by
and
. The following shows that this operation keeps
strongly independent modulo the ideal generated by
. Hence, possibly after a finite (by the Noetherian property of polynomial rings) number of extensions of
, the leading coefficient
of
depends only on
, for all
. For the set of polynomials
, let
be the set of common zeros of elements of
. Both
and
have dimension
, and
, hence any
-dimensional irreducible component of
is also a component of
. Since
does not vanish on any irreducible component of
, it does not vanish on any
-dimensional irreducible component of
. Therefore, the Gröbner basis of
and
contains a polynomial
depending only on
. Let
. To find a solution of (
2), pick its last
coordinates
so that
. For all
,
, and so by
Property 4 if
, for
, is chosen to be the first root of
, then
. Moreover,
, because otherwise
would belong to
, which would imply that
, which is impossible since
divides
.
To prove the correctness of the aforementioned algorithm, it must be shown that extending
by
that depend on a variable not in
preserves strong independence of
modulo the ideal generated by
. Suppose for some
,
depends on a variable, which is not in
. Let
denote the ideal generated by
, and let
denote the ideal generated by
and
. Then
does not contain nonzero elements of
. To prove this, suppose that
where
and
. Then
, with
, and
belongs to the ideal generated by
, and so does
. This contradicts the choice of
since the leading monomial of
depends on
and is strictly smaller than the leading monomial of
. Therefore, the projection of
on
is dense in
, and so, since
has dimension
,
must be zero on some irreducible component
of
whose projection on
is dense in
. Since
is the Zariski closure of the projection of the
-dimensional set
,
is contained in the Zariski closure of the projection of an irreducible component
of
.
has dimension
, hence
is zero on
, and the projection of
on
is dense in
, which proves that
is strongly independent modulo the ideal generated by
and
.
Here is an example in which
needs to be extended. Here
,
,
, and
.
is zero on one of the two one-dimensional components of
.
| Out[16]= |  |
Extending
by
results in all
depending on
only (in fact even constant) while preserving the strong independence of
.
| Out[17]= |  |
Reduce
Reduce can solve arbitrary complex polynomial systems. As the first step,
Reduce uses the
quantifier elimination algorithm to eliminate the quantifiers. If the obtained quantifier-free system is a disjunction, each term of the disjunction is solved separately, and the solution is given as a disjunction of the solutions of the terms. Thus, the problem is reduced to solving quantifier-free systems of the form
First compute the
GroebnerBasis 
of
with variable order
and
, and select the polynomials that do not depend on
. Then the solution set of
is equal to the solution set of (
3) and
does not vanish on any component of the zero set
of
. If
contains 1, (
3) has no solutions. Otherwise for each
, such that the set
of elements of
depending on
and not on any
with
is not empty, select an element
of
with the lowest positive degree in
. If one of the leading coefficients
of
is zero on
, that is, it belongs to the radical of the ideal generated by
, replace
by the lexicographic Gröbner basis of the ideal generated by
and
. Now split the system into
and call the solving procedure recursively on all but the last term of the disjunction (
4). Note that the algebraic set
is strictly contained in
, so the recursion is finite. If the product of all the
and
belongs to the radical of the ideal generated by
, the last term has no solutions. Otherwise, by
Property 4, the solution set of the last term is equal to
The conditions
guarantee that all the solutions (represented as radicals or
Root objects) given by
![Roots[h_(i_j)0,x_(i_j)]](Files/ComplexPolynomialSystems.en/Image_651.gif "Roots[h_(i_j)0,x_(i_j)]")
are well defined.
Reduce performs several operations in order to simplify the inequation conditions returned, like removing multiple factors, removing factors common with earlier inequation conditions, reducing modulo the
, and removing factors that are nonzero on
.
Options
Options for Reduce, Resolve, and FindInstance
The
Mathematica functions for solving complex polynomial systems have a number of options that control the way they operate. This section gives a summary of these options.
| | |
| Backsubstitution | False | whether the solutions given by Reduce and Resolve with specified variables should be unwound by backsubstitution |
| Cubics | False | whether the Cardano formulas should be used to express solutions of cubics |
| Quartics | False | whether the Cardano formulas should be used to express solutions of quartics |
Options of Reduce and Resolve affecting the behavior of complex polynomial systems.
| | |
| WorkingPrecision | ∞ | the working precision to be used in computations, with the default settings of system options; the value of working precision affects only calls to Roots |
Options of Reduce, Resolve, and FindInstance affecting the behavior of complex polynomial systems.
Backsubstitution
By default,
Reduce may use variables appearing earlier in the variable list to express solutions for variables appearing later in the variable list.
| Out[18]= |  |
With
True,
Reduce uses backsubstitution to eliminate variables from the right-hand sides of the equations.
| Out[19]= |  |
Cubics and Quartics
By default
Reduce does not use the Cardano formulas for solving cubics or quartics.
| Out[20]= |  |
Setting the options
Cubics and
Quartics to
True allows
Reduce to use the Cardano formulas for solving cubics and quartics.
| Out[21]= |  |
WorkingPrecision
| Out[22]= |  |
The ReduceOptions Group of System Options
Here are the system options from the
group that may affect the behavior of
Reduce,
Resolve, and
FindInstance for complex polynomial systems. The options can be set with
This sets the option
to
True.
This checks the value of
.
| Out[24]= |  |
This sets the option
back to the default value
False.
| | |
| "FinitePrecisionGB" | False | whether finite values of working precision should be used in calls to GroebnerBasis |
| "ReorderVariables" | False | whether Reduce and Resolve are allowed to reorder the specified variables |
group options that affect the behavior of Reduce, Resolve, and FindInstance for complex polynomial systems.
FinitePrecisionGB
| Out[28]= |  |
| Out[30]= |  |
Using finite precision may significantly improve the speed of
GroebnerBasis computations. However, the numeric computations may fail due to loss of precision, or give incorrect answers. They usually give less precise results than exact
GroebnerBasis computations followed by numeric root finding.
| Out[31]= |  |
This shows that the results are equal up to their precision.
| Out[32]= |  |
ReorderVariables
By default,
Reduce is not allowed to reorder the specified variables. Variables appearing earlier in the variable list may be used to express solutions for variables appearing later in the variable list, but not vice versa.
| Out[34]= |  |
Setting the system option
True allows
Reduce to pick a variable order that makes the equations easier to solve.
| Out[35]= |  |
References
[1] Becker, T. and V. Weispfenning. Gröbner Bases. Springer-Verlag, 1993.
[2] Cox, D., J. Little, and D. O'Shea. Ideals, Varieties, and Algorithms. 2nd ed., Springer-Verlag, 1997.
[3] Łojasiewicz, S. Introduction to Complex Analytic Geometry. Birkhaüser, 1991.
Automatic. This means that even with WorkingPrecision set to a finite number 
, if the input is exact GroebnerBasis uses exact computations.
