|Introduction||Arbitrary Complex Polynomial Systems|
The Wolfram Language 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.
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.
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
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).
Resolve can eliminate quantifiers from arbitrary complex polynomial systems. If no variables are specified, the result is a logical combination of terms
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 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 the Wolfram Language in solving complex polynomial systems. For a more complete presentation see, for example, [1, 2]. Note that what  calls a monomial,  calls a term, and vice versa. This tutorial uses the terminology of .
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 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  for a proof).
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.
The Wolfram Language 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 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.
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.
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 .
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
|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.
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|
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 .
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 CoefficientDomain->Rationals and .
|find a Gröbner basis in and use the Gröbner walk algorithm to transform it to a Gröbner basis in|
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.
Using requires the GroebnerBasis syntax with elimination variables specified.
|find a Gröbner basis in|
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. (The Wolfram Language 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|
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.
By Hilbert's Nullstellensatz and Property 3 of Gröbner bases
When the Wolfram Language 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 the Wolfram Language uses .
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 . Quantifier elimination is the procedure of finding a quantifier-free complex polynomial system equivalent to a given complex polynomial system. In the Wolfram Language, 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.
To eliminate the quantifier from (1), the Wolfram Language first computes the Gröbner basis of equations
The monomial order used is , 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.
be the pseudoremainder of the division of by as polynomials in . Then (3) is equivalent to the quantifier-free system
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 ,
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
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 (, Section 9.3). Reorder so that , and compute the lexicographic order GroebnerBasis of the ideal generated by . To compute , the Wolfram Language 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 .
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 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 .
|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|
|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|
|"AlgebraicNumberOutput"||True||whether Reduce should output AlgebraicNumber objects instead of polynomials in one Root object|
|"FinitePrecisionGB"||False||whether finite values of working precision should be used in calls to GroebnerBasis|
|"ReorderVariables"||Automatic||whether Reduce, Resolve, and Solve are allowed to reorder the specified variables|
|"UseNestedRoots"||Automatic||whether Root objects representing algebraic numbers defined by triangular systems of equations can be used in the output|
For systems with equational constraints generating a zero-dimensional ideal , the Wolfram Language uses a variant of the CAD algorithm that finds projection polynomials using Gröbner basis methods. If the lexicographic order Gröbner basis of contains linear polynomials with constant coefficients in every variable but the last one (which is true "generically"), then all coordinates of a solution are polynomials in one algebraic number, namely the last coordinate. The setting of determines whether Reduce represents the solution coordinates as AlgebraicNumber objects in the field generated by the last coordinate.