MATHEMATICA TUTORIAL

Real Polynomial Systems

Introduction

A real polynomial system is an expression constructed with polynomial equations and inequalities

combined using logical connectives and quantifiers

An occurrence of a variable inside or is called a bound occurrence; any other occurrence of is called a free occurrence. A variable is called a free variable of a real polynomial system if the system contains a free occurrence of . A real polynomial system is quantifier free if it contains no quantifiers.

An example of a real polynomial system with free variables , , and is the following:

Any real polynomial system can be transformed to the prenex normal form

where each is or , and is a quantifier-free formula called the quantifier-free part of the system.

Any quantifier-free real polynomial system can be transformed to the disjunctive normal form

where each is a polynomial equation or inequality.

Reduce, Resolve, and FindInstance always put real polynomial systems in the prenex normal form, with quantifier-free parts in the disjunctive normal form, and subtract sides of equations and inequalities to put them in the form

In this tutorial, it is always assumed the system has been transformed to this form.

Reduce can solve arbitrary real polynomial systems. For a system with free variables , the solution (possibly after expanding with respect to ) is a disjunction of terms of the form

where is one of

and and are algebraic functions (expressed using Root objects or radicals) such that for all satisfying , and are well defined (that is, denominators and leading terms of Root objects are nonzero), real valued, continuous, and satisfy inequality .

The subset of described by formula (4) is called a cell. The cells described by different terms of solution of a real polynomial system are disjoint.

This solves the system (1). The cells are represented in a nested form.
In[1]:=
Click for copyable input
Out[1]=
This defines a function expanding with respect to .
In[2]:=
Click for copyable input
Here is the solution of the system (1) written explicitly as a union of disjoint cells.
In[5]:=
Click for copyable input
Out[5]=

Resolve can eliminate quantifiers from arbitrary real polynomial systems. If no variables are specified in the input and all input polynomials are at most quadratic in the bound variables, Resolve may be able to eliminate the quantifiers without solving the resulting system. Otherwise, Resolve uses the same algorithm and gives the same answer as Reduce.

This eliminates quantifiers from the system (1).
In[6]:=
Click for copyable input
Out[6]=

FindInstance can handle arbitrary real polynomial systems, giving instances of real 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 may depend on the value of the option. If one instance is requested and the system does not contain general () quantifiers, a faster algorithm producing one instance is used and the instance returned is always the same.

This finds a solution of the system (1).
In[7]:=
Click for copyable input
Out[7]=

The main general tool used in solving real polynomial systems is the Cylindrical Algebraic Decomposition (CAD) algorithm (see, for example, [1]). CAD for real polynomial systems is available in Mathematica directly as CylindricalDecomposition. There are also several other algorithms used to solve special case problems.

Cylindrical Algebraic Decomposition

Semialgebraic Sets and Cell Decomposition

A subset of is semialgebraic if it is a solution set of a quantifier-free real polynomial system. According to Tarski's theorem [2], solution sets of arbitrary (quantified) real polynomial systems are semialgebraic.

Every semialgebraic set can be represented as a finite union of disjoint cells [3] defined recursively as follows:

  • A cell in is a point or an open interval
    • A cell in has one of the two forms

    where is a cell in , is a continuous algebraic function, and are continuous algebraic functions, or or , and on .

    By an algebraic function we mean a function for which there is a polynomial

    such that

    In Mathematica algebraic functions can be represented as Root objects or radicals.

    The CAD algorithm, introduced by Collins [4], computes a cell decomposition of solution sets of arbitrary real polynomial systems. The objective of the original Collins algorithm was to eliminate quantifiers from a quantified real polynomial system and to produce an equivalent quantifier-free polynomial system. After finding a cell decomposition, the algorithm performed an additional step of finding an implicit representation of the semialgebraic set in terms of polynomial equations and inequalities in the free variables. The objective of Reduce is somewhat different. Given a semialgebraic set presented by a real polynomial system, quantified or not, Reduce finds a cell decomposition of the set, explicitly written in terms of algebraic functions.

    While Reduce may use other methods to solve the system, CylindricalDecomposition gives a direct access to the CAD algorithm. For a real polynomial system, CylindricalDecomposition gives a nested formula representing disjunction of cells in the solved form (4). As in the output of Reduce, the cells are disjoint and additionally are always ordered lexicographically with respect to ranges of the subsequent variables.

    This finds a cell decomposition of an annulus.
    In[8]:=
    Click for copyable input
    Out[8]=

    SemialgebraicComponentInstances gives at least one sample point in each connected component of a semialgebraic set. The function uses the CAD algorithm and returns a sample point in each of the constructed cells.

    This gives a sample point in each element of a cell decomposition of an annulus.
    In[9]:=
    Click for copyable input
    Out[9]=

The Projection Phase of the CAD Algorithm

Finding a cell decomposition of a semialgebraic set using the CAD algorithm consists of two phases, projection and lifting. In the projection phase, we start with the set of factors of the polynomials present in the quantifier-free part of the system (2) and eliminate variables one by one using a projection operator such that

Generally speaking, if all polynomials of have constant signs on a cell , then all polynomials of are delineable over , that is, each has a fixed number of real roots on as a polynomial in , the roots are continuous functions on , they have constant multiplicities, and two roots of two of the polynomials are equal either everywhere or nowhere in . Variables are ordered so that

This way the roots of polynomials of are the algebraic functions needed in the construction of the cell decomposition of the semialgebraic set.

Several improvements have reduced the size of the original Collins projection. The currently best projection operator applicable in all cases is due to Hong [5]; however, in most situations we can use a smaller projection operator given by McCallum [6, 7], with an improvement by Brown [8]. There are even smaller projection operators that can be applied in some special cases. When equational constraints are present, we can use the projection operator suggested by Collins [9], and developed and proven by McCallum [10, 11]. When there are no equations and only strict inequalities, and there are no free variables or we are interested only in the full-dimensional part of the semialgebraic set, we can use an even smaller projection operator described in [12, 13]. For systems containing equational constraints that generate a zero-dimensional ideal, Gröbner bases are used to find projection polynomials.

Mathematica uses the smallest of the previously mentioned projections that is appropriate for the given example. Whenever applicable, we use the equational constraints; otherwise, we attempt to use McCallum's projection with Brown's improvement. When the system does not turn out to be well oriented, we compute Hong's projection.

The Lifting Phase of the CAD Algorithm

In the lifting phase, we find a cell decomposition of the semialgebraic set. Generally speaking, although the actual details depend on the projection operator used, we start with cells in consisting of all distinct roots of and the open intervals between the roots. We find a sample point in each of the cells and remove the cells whose sample points do not satisfy the system describing the semialgebraic set (the system may contain conditions involving only ). Next we lift the cells to cells in , one dimension at a time. Suppose we have lifted the cells to . To lift a cell to , we find the real roots of with replaced with the coordinates of the sample point in . Since the polynomials of are delineable on , each root is a value of a continuous algebraic function at , and the function can be represented as a ^(th) root of a polynomial such that is the ^(th) root of . Now the lifting of the cell to will consist of graphs of these algebraic functions and of the slices of × between the subsequent graphs. The sample points in each of the new cells will be obtained by adding the ^(st) coordinate to , equal to one of the roots, or to a number between two subsequent roots. As in the first step, we remove those lifted cells whose sample points do not satisfy the system describing the semialgebraic set.

If , is a quantifier variable and we may not need to construct all the lifted cells. All we need is to find the (necessarily constant) truth value of on . If , we know that the value is True as soon as the truth value of on one of the lifted cells is True. If , we know that the value is False as soon as the truth value of on one of the lifted cells is False.

The coefficients of sample points computed this way are in general algebraic numbers. To save costly algebraic number computations, Mathematica uses arbitrary-precision floating-point number (Mathematica "bignum") approximations of the coefficients, whenever the results can be validated. Note that using approximate arithmetic may be enough to prove that two roots of a polynomial or a pair of polynomials are distinct, and to find a nonzero sign of a polynomial at a sample point. What we cannot prove with approximate arithmetic is that two roots of a polynomial or a pair of polynomials are equal, or that a polynomial is zero at a sample point. However, we can often use information about the origins of the cell to resolve these problems. For instance, if we know that the resultant of two polynomials vanishes on the cell, and these two polynomials have exactly one pair of complex roots that can be equal within the precision bounds, we can conclude that these roots are equal. Similarly, if the last coordinate of a sample point was a root of a factor of the given polynomial, we know that this polynomial is zero at the sample point. If we cannot resolve all the uncertainties using the collected information about the cell, we compute the exact algebraic number values of the coordinates. For more details, see [14, 24].

Decision Problems, FindInstance, and Assumptions

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 inequalities has solutions.

All algorithms used by Mathematica to solve real polynomial decision problems are capable of producing a point satisfying if the system has solutions. Therefore the algorithms discussed in this section are used not only in Reduce and Resolve for decision problems, but also in FindInstance, whenever a single instance is requested and the system is quantifier free or contains only existential quantifiers. The algorithms discussed here are also used for inference testing by Mathematica functions using assumptions such as Simplify, Refine, Integrate, and so forth.

Solving this decision problem proves that the set contains the disk of radius 4/5 centered at the origin.
In[10]:=
Click for copyable input
Out[10]=
This shows that does not contain the unit disk and provides a counterexample: a point in the unit disk that does not belong to .
In[11]:=
Click for copyable input
Out[11]=

The primary method that allows Mathematica to solve arbitrary real polynomial decision problems is the Cylindrical Algebraic Decomposition (CAD) algorithm. There are, however, several other special case algorithms that provide much better performance in cases in which they are applicable.

When all polynomials are linear with rational number or floating-point number coefficients, Mathematica uses a method based on the simplex linear programming method. For other linear systems, Mathematica uses a variant of the Loos-Weispfenning linear quantifier elimination algorithm [15]. When the system contains no equations and only strict inequalities, a faster "generic" version of CAD is used [12, 13]. For systems containing equational constraints that generate a zero-dimensional ideal, Mathematica uses Gröbner bases to find a solution. For nonlinear systems with floating-point number coefficients, an inexact coefficient version of CAD [16] is used.

There are also some special case methods that can be used as preprocessors to other decision methods. When the system contains an equational constraint linear with a constant coefficient in one of the variables, the constraint is used to eliminate the linear variable. If there is a variable that appears in the system only linearly with constant coefficients, the variable is eliminated using the Loos-Weispfenning linear quantifier elimination algorithm [15]. If there is a variable that appears in the system only quadratically, the quadratic case of Weispfenning's quantifier elimination by virtual substitution algorithm [22, 23] could be used to eliminate the variable. For some examples this gives a substantial speedup; however, quite often it results in a significant slowdown. By default, the algorithm is not used as a preprocessor. Setting the system option QVSPreprocessor in the group to True makes Mathematica use it.

There are two other special cases of real decision algorithms available in Mathematica. An algorithm by Aubry, Rouillier, and Safey El Din [17] applies to systems containing only equations. There are examples for which the algorithm performs much better than CAD; however, for randomly chosen systems of equations, it seems to perform significantly worse; therefore, it is not used by default. Setting the system option ARSDecision in the group to True causes Mathematica to use the algorithm. Another algorithm by G. X. Zeng and X. N. Zeng [18] applies to systems that consist of a single strict inequality. Again, the algorithm is faster than CAD for some examples, but slower in general; therefore, it is not used by default. Setting the system option ZengDecision in the group to True causes Mathematica to use the algorithm.

Arbitrary Real Polynomial Systems

Solving Real Polynomial Systems

According to Tarski's theorem [2], the solution set of an arbitrary (quantified) real polynomial system is a semialgebraic set. Reduce gives a description of this set in the solved form (4).

This shows for what the set contains the disk of radius centered at the origin.
In[12]:=
Click for copyable input
Out[12]=
This gives the projection of on the plane along the axis.
In[13]:=
Click for copyable input
Out[13]=
This finds the projection of Whitney's umbrella on the plane along the axis.
In[14]:=
Click for copyable input
Out[14]=
Here we find the interior of the previous projection set by directly using the definition.
In[15]:=
Click for copyable input
Out[15]=

Quantifier Elimination

The objective of Resolve with no variables specified is to eliminate quantifiers and produce an equivalent quantifier-free formula. The formula may or may not be in a solved form, depending on the algorithm used.

Producing a fully solved quantifier-free formula here is difficult because of the complexity of polynomials in , , and appearing in the input. However, since appears in the input polynomials only linearly, the quantifier can be quickly eliminated using the Loos-Weispfenning linear quantifier elimination algorithm, which depends very little on the complexity of coefficients.
In[16]:=
Click for copyable input
Out[16]=

Algorithms

The primary method used by Mathematica for solving real polynomial systems and real quantifier elimination is the CAD algorithm. There are, however, simpler methods applicable in special cases.

If the system contains an equational constraint in a variable from the innermost quantifier, the constraint is used to simplify the system using the identity

Note that if or is a nonzero constant, this eliminates the variable .

If all polynomials in the system are linear in a variable from the innermost quantifier, the variable is eliminated using the Loos-Weispfenning linear quantifier elimination algorithm [15].

If all polynomials in the system are at most quadratic in a variable from the innermost quantifier, the variable is eliminated using the quadratic case of Weispfenning's quantifier elimination by virtual substitution algorithm [22, 23]. With the default setting of the system option QuadraticQE, the algorithm is used for Resolve with no variables specified and with at least two parameters present, and for Reduce and Resolve with at least three variables as long as elimination of one variable at most doubles the LeafCount of the system.

The CAD algorithm is used when the previous three special case methods are no longer applicable, but there are still quantifiers left to eliminate or a solution is required.

For systems containing equational constraints that generate a zero-dimensional ideal, Mathematica uses Gröbner bases to find the solution set.

Options

The Mathematica functions for solving real polynomial systems have a number of options that control the way that they operate. This section gives a summary of these options.

option name
default value
CubicsFalsewhether the Cardano formulas should be used to express numeric solutions of cubics
QuarticsFalsewhether the Cardano formulas should be used to express numeric solutions of quartics
WorkingPrecisionthe working precision to be used in computations

Reduce, Resolve, and FindInstance options affecting the behavior for real polynomial systems.

Cubics and Quartics

By default, Reduce does not use the Cardano formulas for solving cubics or quartics over the reals.
In[17]:=
Click for copyable input
Out[17]=
Setting options Cubics and Quartics to True makes Reduce use the Cardano formulas to represent numeric solutions of cubics and quartics.
In[18]:=
Click for copyable input
Out[18]=
Solutions of cubics and quartics involving parameters will still be represented using Root objects.
In[19]:=
Click for copyable input
Out[19]=
This is because the Cardano formulas do not separate real solutions from nonreal ones. For instance, in this case, for the third radical solution is real, but for the first radical solution is real.
In[20]:=
Click for copyable input
Out[20]=
In[21]:=
Click for copyable input
Out[21]=

WorkingPrecision

The setting of WorkingPrecision affects the lifting phase of the CAD algorithm. With a finite working precision prec, sample points in the first variable lifted are represented as arbitrary-precision floating-point numbers with prec digits of precision. When we compute sample points for subsequent variables, we find roots of polynomials whose coefficients depend on already computed sample point coordinates and therefore may be inexact. Hence coordinates of sample points will have precision prec or lower. Determining the sign of polynomials at sample points is simply done by evaluating Sign of the floating-point number obtained after the substitution. Using a finite WorkingPrecision may allow getting the answer faster; however, the answer may be incorrect or the computation may fail due to loss of precision.

Here Reduce working with WorkingPrecision->30 finds the correct solution somewhat faster than when working with infinite WorkingPrecision.
In[22]:=
Click for copyable input
Out[22]=
In[23]:=
Click for copyable input
Out[23]=

ReduceOptions Group of System Options

Here are the system options from the group that may affect the behavior of Reduce, Resolve, and FindInstance for real polynomial systems. The options can be set with

SetSystemOptions["ReduceOptions"->{"option name"->value}].
option name
default value
"AlgebraicNumberOutput"Truewhether Reduce should output AlgebraicNumber objects instead of polynomials in one Root object
"FactorInequalities"Falsewhether inequalities should be factored at the input preprocessing stage
"ReorderVariables"Automaticwhether Reduce, Resolve, and Solve are allowed to reorder the specified variables
"UseNestedRoots"Automaticwhether Root objects representing algebraic numbers defined by triangular systems of equations can be used in the output

group options affecting the behavior of Reduce, Resolve, and FindInstance for real polynomial systems.

AlgebraicNumberOutput

For systems with equational constraints generating a zero-dimensional ideal , Mathematica 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.

By default, the solution coordinates are represented as AlgebraicNumber objects.
In[24]:=
Click for copyable input
Out[24]=
With AlgebraicNumberOutput->False, the solution coordinates are given as polynomials in a Root object.
In[25]:=
Click for copyable input
Out[26]=
In[27]:=
Click for copyable input

FactorInequalities

Using transformations

at the input preprocessing stage may speed up the computations in some cases. In general, however, it does not make the problem easier to solve, and, in some cases, it may make the problem significantly harder. By default, these transformations are not used.

Here Reduce does not use transformations (7).
In[28]:=
Click for copyable input
Out[30]=
Using transformations (7) speeds up the first example; however, it makes the second example significantly slower. The second example suffers from exponential growth of the number of inequalities.
In[31]:=
Click for copyable input
Out[34]=
In[35]:=
Click for copyable input

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.
In[36]:=
Click for copyable input
Out[36]=
Setting the system option ReorderVariables->True allows Reduce to pick a variable order that makes the system easier to solve.
In[37]:=
Click for copyable input
Out[38]=
In[39]:=
Click for copyable input
By default, Solve is allowed to reorder the specified variables. In this example it is easier to solve for first and express in terms of the solution for .
In[40]:=
Click for copyable input
Out[40]=
Setting the system option ReorderVariables->False makes Solve use the specified variable order.
In[41]:=
Click for copyable input
Out[42]=
In[43]:=
Click for copyable input

UseNestedRoots

By default, Reduce may express solutions in terms of Root objects representing algebraic numbers defined by triangular systems of equations.
In[44]:=
Click for copyable input
Out[44]=
Setting the system option UseNestedRoots->False makes Reduce use algebraic numbers defined by univariate equations.
In[45]:=
Click for copyable input
Out[46]=
Finding minimal polynomials for all solution coordinates may be slow.
In[47]:=
Click for copyable input
Out[48]=
In[49]:=
Click for copyable input
Out[50]=
Setting UseNestedRoots->True allows Reduce to use algebraic numbers defined by triangular systems that are linear in the last variable.
In[51]:=
Click for copyable input
Out[52]=
With the default setting UseNestedRoots->Automatic, Reduce represents the second coordinate as a polynomial in the first coordinate.
In[53]:=
Click for copyable input
Out[54]=

InequalitySolvingOptions Group of System Options

Here are the system options from the group that may affect the behavior of Reduce, Resolve, FindInstance, and CylindricalDecomposition for real polynomial systems. The options can be set with

SetSystemOptions["InequalitySolvingOptions"->{"option name"->value}].
option name
default value
"ARSDecision"Falsewhether to use the decision algorithm given in [17]
"BrownProjection"Truewhether the CAD algorithm should use the improved projection operator given in [8]
"CAD"Truewhether to use the CAD algorithm
"CADBacksubstitution"Automaticwhether the CAD algorithm should backsubstitute numeric values of solution coordinates
"CADCombineCells"Truewhether the output of the CAD algorithm should be simplified by combining adjacent cells over which the solution formulas are identical
"CADDefaultPrecision"30.103the initial precision to which nonrational roots are computed in the lifting phase of the CAD algorithm; if the computation with approximate roots cannot be validated, the algorithm raises the precision by the value of ; if this does not resolve the issue, the algorithm reverts to exact algebraic number computation
"CADExtraPrecision"30.103the amount of extra precision to be used in the lifting phase of the CAD algorithm
"CADMethod"Automaticspecifies the CAD computation method used by CylindricalDecomposition
"CADSortVariables"Truewhether the CAD algorithm should use variable reordering heuristics for quantifier variables within a single quantifier or in decision problems
"CADZeroTest"{0,∞}determines the zero testing method used by the CAD algorithm for expressions obtained by evaluating polynomials at points with algebraic number coordinates
"EquationalConstraintsCAD"Automaticwhether the projection phase of the CAD algorithm should use equational constraints; with the default Automatic setting the operator proven correct in [11] is used; if True the unproven projection operator using multiple equational constraints suggested in [4] is used
"FGLMBasisConversion"Falsewhether the CAD algorithm should use a Gröbner basis conversion algorithm based on [20] to find univariate polynomials in zero-dimensional Gröbner bases; otherwise, is used
"FGLMElimination"Automaticwhether the decision and quantifier elimination algorithms for systems with equational constraints forming a zero-dimensional ideal should use an algorithm based on [20] to look for linear equation constraints (with constant leading coefficients) in one of the variables to be used for elimination
"GenericCAD"Truewhether to use the variant of the CAD algorithm described in [13] for decision and optimization problems
"GroebnerCAD"Truewhether the CAD algorithm for systems with equational constraints forming a zero-dimensional ideal should use Gröbner bases as projection
"LinearDecisionMethodCrossovers"
{0,30,20,Automatic}determines methods used to find solutions of systems of linear equations and inequalities with rational number coefficients
"LinearEquations"Truewhether to use linear equation constraints (with constant leading coefficients) to eliminate variables in decision problems
"LinearQE"Truewhether to use the Loos-Weispfenning linear quantifier elimination algorithm [15] for quantifier elimination problems
"LWDecision"Truewhether to use the Loos-Weispfenning linear quantifier elimination algorithm [15] for decision problems with linear inequality systems
"LWPreprocessor"Automaticwhether to use the Loos-Weispfenning linear quantifier elimination algorithm [15] as a preprocessor for the decision problems
"ProjectAlgebraic"Automaticwhether the CAD algorithm should compute projections with respect to variables replacing algebraic number coefficients or use their minimal polynomials instead
"ProveMultiplicities"Truedetermines the way in which the lifting phase of the CAD algorithm validates multiple roots and zero leading coefficients of projection polynomials
"QuadraticQE"Automaticwhether to use the quadratic case of Weispfenning's quantifier elimination by virtual substitution algorithm in quantifier elimination
"QVSPreprocessor"Falsewhether to use the quadratic case of Weispfenning's quantifier elimination by virtual substitution algorithm as a preprocessor for the decision problems
"ReducePowers"Automaticwhether to replace with in the input to the CAD, where is the GCD of all exponents of in the system
"RootReduced"Falsewhether the coordinates of solutions of systems with equational constraints forming a zero-dimensional ideal should be reduced to single Root objects
"Simplex"Truewhether to use the simplex algorithm in the decision algorithm for linear inequality systems
"SimplifyInequalities"Automaticwhether to use the inequality simplification heuristic presented in [25]
"ThreadOr"Truewhether to solve each case of disjunction separately in decision problems, optimization, and in quantifier elimination of existential quantifiers when the quantifier-free system does not need to be solved
"ZengDecision"Falsewhether to use the decision algorithm given in [18]

group options affecting the behavior of Reduce, Resolve, and FindInstance for real polynomial systems.

ARSDecision

The option specifies whether Mathematica should use the algorithm by Aubry, Rouillier, and Safey El Din [17]. The algorithm applies to decision problems containing only equations. There are examples for which the algorithm performs much better than the CAD algorithm; however, for randomly chosen systems of equations it seems to perform significantly worse. Therefore it is not used by default. Here is a decision problem (referred to as butcher8 in the literature), which is not done by CAD in 1000 seconds, but which can be done quite fast by the algorithm given in [17].
In[55]:=
Click for copyable input
Out[55]=
In[56]:=
Click for copyable input

BrownProjection

By default, the Mathematica implementation of the CAD algorithm uses Brown's improved projection operator [8]. The improvement usually speeds up computations substantially. There are some cases where using Brown's projection operator results in a slight slowdown. The option specifies whether Brown's improvement should be used. In the first example [21], using Brown's improved projection operator results in a speedup; in the second, it results in a slowdown.
In[57]:=
Click for copyable input
Out[61]=
In[62]:=
Click for copyable input
In[63]:=
Click for copyable input
Out[65]=
In[66]:=
Click for copyable input

CAD

The option specifies whether Mathematica is allowed to use the CAD algorithm. With set to False, computations that require CAD will fail immediately instead of attempting the high complexity CAD computation. With CAD enabled, this computation is not done in 1000 seconds.
In[67]:=
Click for copyable input
Out[68]=
In[69]:=
Click for copyable input

CADBacksubstitution

By default, Mathematica backsubstitutes rational values of solution coordinates in the CAD algorithm. Other numeric values are not backsubstituted.
In[70]:=
Click for copyable input
Out[70]=
In[71]:=
Click for copyable input
Out[71]=
With CADBacksubstitution->True, all numeric values of solution coordinates are backsubstituted.
In[72]:=
Click for copyable input
Out[73]=
In[74]:=
Click for copyable input
Out[74]=
With CADBacksubstitution->False, Mathematica does not backsubstitute coordinate values in the CAD algorithm.
In[75]:=
Click for copyable input
Out[76]=
In[77]:=
Click for copyable input
Out[77]=
In[78]:=
Click for copyable input

CADCombineCells

By default, Mathematica simplifies the result of the CAD algorithm by combining adjacent cells over which the solution formulas are identical. Here the solution formula for is the same for all real , even though the solution set is not connected.
In[79]:=
Click for copyable input
Out[79]=
In[80]:=
Click for copyable input
Out[80]=
With CADCombineCells->Automatic, Mathematica combines adjacent cells over which the solution formulas are identical only when the solution formulas do not contain Root functions. This guarantees that, after distributing conjunction over disjunction in the result of CylindricalDecomposition, each conjunction describes a connected set.
In[81]:=
Click for copyable input
Out[82]=
The projection polynomials may not be delineable over the combined cells. For instance, here and have a common root at , but have no common roots at other points of the interval .
In[83]:=
Click for copyable input
Out[83]=
With CADCombineCells->False, Mathematica does not combine CAD cells.
In[84]:=
Click for copyable input
Out[85]=
In[86]:=
Click for copyable input

CADDefaultPrecision and CADExtraPrecision

By default, Mathematica uses validated numeric computations in the lifting phase of the CAD algorithm, reverting to exact algebraic number computations only if the numeric computations cannot be validated [14, 24]. The option specifies the initial precision with which the sample point coordinates are computed. If the computations performed with this precision cannot be validated, the algorithm raises the precision by the value of . If this does not resolve the issue, the algorithm reverts to exact algebraic number computation. Choosing the values of and is a tradeoff between the speed of numeric computations and the number of points where the algorithm reverts to exact computations due to precision loss. With the default values of 100 bits, the cases where the algorithm needs to revert to exact computations due to precision loss seem quite rare. Setting to Infinity causes Mathematica to use exact algebraic number computations in the lifting phase of CAD. Here is an example that runs fastest with the lowest setting. (Specifying values lower than 16.2556 (54 bits) results in being set to 16.2556.) With CADDefaultPrecision->Infinity, the example did not finish in 1000 seconds.
In[87]:=
Click for copyable input
Out[87]=
In[88]:=
Click for copyable input
Out[89]=
In[90]:=
Click for copyable input

CADMethod

The setting of determines the CAD computation method used by CylindricalDecomposition. It does not affect other functions using the CAD algorithm. The default setting CADMethod->Automatic is a combination of the Direct and settings.

With , CylindricalDecomposition computes a cylindrical algebraic decomposition by a single application of the CAD algorithm to the input formula transformed to the prenex format.
In[91]:=
Click for copyable input
Out[92]=
With , CylindricalDecomposition subdivides the input formula, computes a CAD of each subformula, and then combines the results using the algorithm of [26].
In[93]:=
Click for copyable input
Out[94]=
If the input formula is a conjunction then, with , CylindricalDecomposition computes a CAD of the first element of the conjunction and then adds the subsequent elements of the conjunction using the algorithm of [27].
In[95]:=
Click for copyable input
Out[96]=
In[97]:=
Click for copyable input
Out[98]=
In[99]:=
Click for copyable input

CADSortVariables

The performance of the CAD algorithm often depends quite strongly on the order of variables used. Some aspects of the variable ordering are fixed by the problem we are solving: quantifier variables need to be projected before free variables, and variables from innermost quantifiers need to be projected first. Variables specified in Reduce and Resolve cannot be reordered unless is set to True. This, however, still leaves some freedom in ordering of variables: variables from the same quantifier can be reordered, and so can be variables given to FindInstance. By default, Mathematica uses a variable ordering heuristic to determine the order of these variables. In most cases the heuristic improves the performance of CAD; in some examples, however, the heuristic does not pick the best ordering. Setting to False disables the heuristic and the order of variables used is as given in the quantifier variable list or in the variable list argument to FindInstance. Here is an example [21] that without reordering of quantified variables does not finish in 1000 seconds.
In[100]:=
Click for copyable input
Out[100]=
This shows the optimal variable ordering for the example.
In[101]:=
Click for copyable input
In[102]:=
Click for copyable input
Out[102]=
In[103]:=
Click for copyable input

CADZeroTest

The setting of this option affects the lifting phase of the CAD algorithm when sample points with exact algebraic number coordinates are used. By default Mathematica uses sample points with arbitrary-precision floating-point number coordinates and validates the results using the methods of [14, 24]. Sample points with exact algebraic number coordinates are used only if the results of approximate computation cannot be validated or if CADDefaultPrecision is set to Infinity.

To determine the sign of a polynomial evaluated at a sample point with algebraic number coordinates, we first evaluate the polynomial at numeric approximations of the algebraic numbers. If the result is nonzero (that is, zero is not within the error bounds of the resulting approximate number), we know the sign. Otherwise, we need to test whether a polynomial expression in algebraic numbers is zero. The value of the option specifies what zero testing method should be used at this moment. The value should be a pair . With the default value Mathematica computes an accuracy such that if the expression is zero up to this accuracy, it must be zero. If , the value of the expression is computed up to accuracy and its sign is checked. Otherwise, the expression is represented as a single Root object using RootReduce and the sign of the Root object is found. With the default value we revert to RootReduce if eacc>$MaxPrecision. If , RootReduce is always used. If , expressions that are zero up to accuracy are considered zero. This is the fastest method, but, unlike the other two, it may give incorrect results because expressions that are nonzero but close to zero may be treated as zero.

With CADDefaultPrecision->Infinity the CAD algorithm uses sample points with exact algebraic number coordinates.
In[104]:=
Click for copyable input
Out[105]=
The example runs faster with the CAD algorithm using the 30 digits of accuracy numeric zero test. The result in this example is correct; however, this setting of may lead to incorrect results.
In[106]:=
Click for copyable input
Out[107]=
With the default settings of the system options, this example runs much faster.
In[108]:=
Click for copyable input
Out[110]=

EquationalConstraintsCAD

The option specifies whether the projection phase of the CAD algorithm should use equational constraints. With the default setting Automatic, Mathematica uses the projection operator proven correct in [11]. With EquationalConstraintsCAD->True, the smaller but unproven projection operator suggested in [4] is used.

Here we find an instance satisfying the system using the CAD algorithm with EquationalConstraintsCAD->True. Even though the method used to find the solution was based on an unproven conjecture, the solution is proven to be correct, that is, it satisfies the input system.
In[111]:=
Click for copyable input
Out[112]=
With the default setting EquationalConstraintsCAD->Automatic, finding a solution of this system takes somewhat longer.
In[113]:=
Click for copyable input
Out[114]=
With EquationalConstraintsCAD->False, finding a solution of this system takes much longer.
In[115]:=
Click for copyable input
Out[116]=
Here FindInstance shows that the system has no solutions. Since it is using the CAD algorithm with EquationalConstraintsCAD->True, the correctness of the answer depends on an unproven conjecture.
In[117]:=
Click for copyable input
Out[118]=
With the default setting EquationalConstraintsCAD->Automatic, proving that the system has no solutions takes longer, but the answer is known to be correct.
In[119]:=
Click for copyable input
Out[120]=

FGLMBasisConversion

For systems with equational constraints generating a zero-dimensional ideal , Mathematica uses a variant of the CAD algorithm that finds projection polynomials using Gröbner basis methods. If the lexicographic order Gröbner basis of does not contain linear polynomials with constant coefficients in every variable but the last one and UseNestedRoots is set to False, then for every variable we find a univariate polynomial in that belongs to . Mathematica can do this in two ways. By default, it uses a method based on computations. Setting to True causes Mathematica to use a method based on [20].

The method based on [20] seems to be slightly slower in general.
In[121]:=
Click for copyable input
Out[125]=
In[126]:=
Click for copyable input

FGLMElimination

The option specifies whether Mathematica should use a special case heuristic applicable to systems with equational constraints generating a zero-dimensional ideal . The heuristic uses a method based on [20] to find in polynomials that are linear (with a constant coefficient) in one of the quantified variables and uses such polynomials for elimination. The method can be used both in the decision algorithm and in quantifier elimination. With the default Automatic setting, it is used only in Resolve with no "solve" variables specified and for systems with at least two free variables.

This by default uses the elimination method based on [20], and returns a quantifier-free system in an unsolved form.
In[128]:=
Click for copyable input
Out[128]=
With set to False, the example takes longer to compute and the answer is in a solved form. (We show N of the answer for better readability.)
In[129]:=
Click for copyable input
Out[130]=
If there is only one free variable, Resolve by default does not use the elimination method based on [20]. (We show N of the answer for better readability.)
In[131]:=
Click for copyable input
Out[132]=
With set to True, the example takes longer to compute and the answer is given in an unsolved form.
In[133]:=
Click for copyable input
Out[134]=
In[135]:=
Click for copyable input

GenericCAD

Mathematica uses a simplified version of the CAD algorithm described in [13] to solve decision problems or find solutions of real polynomial systems that do not contain equations. The method finds a solution or proves that there are no solutions if all inequalities in the system are strict ( or ). The method is also used for systems containing weak ( or ) inequalities. In this case, if it finds a solution of the strict inequality version of the system, it is also a solution of the original system. However, if it proves that the strict inequality version of the system has no solutions, the full version of the CAD algorithm is needed to decide whether the original system has solutions. The system option specifies whether Mathematica should use the method.

Here the method finds a solution of the strict inequality version of the system.
In[136]:=
Click for copyable input
Out[136]=
Without , finding a solution of the system takes much longer.
In[137]:=
Click for copyable input
Out[138]=
In[139]:=
Click for copyable input
This system has no solutions and contains weak inequalities. After the method finds no solutions of the strict inequality version of the system, Mathematica needs to run the full CAD to prove that there are no solutions.
In[140]:=
Click for copyable input
Out[140]=
Running the same example with GenericCAD->False allows to save the time previously used by the computation.
In[141]:=
Click for copyable input
Out[142]=
In[143]:=
Click for copyable input
This system contains only strict inequalities, so can prove that it has no solutions.
In[144]:=
Click for copyable input
Out[144]=
Without , it takes much longer to prove that the system has no solutions.
In[145]:=
Click for copyable input
Out[146]=
In[147]:=
Click for copyable input

GroebnerCAD

For systems with equational constraints generating a zero-dimensional ideal , Mathematica uses a variant of the CAD algorithm that finds projection polynomials using Gröbner basis methods. Setting to False, causes Mathematica to use the standard CAD projection instead.

With GroebnerCAD->False, this example runs much slower.
In[148]:=
Click for copyable input
Out[148]=
In[149]:=
Click for copyable input
In[150]:=
Click for copyable input
Out[150]=
This checks that the solutions are equivalent.
In[151]:=
Click for copyable input
Out[151]=
In[152]:=
Click for copyable input

LinearDecisionMethodCrossovers, LWDecision, and Simplex

These three options specify methods used to solve decision problems or find solution instances for systems of linear equations and inequalities. The available methods are the Loos-Weispfenning algorithm [15], the simplex algorithm, and the revised simplex algorithm. All three methods can handle systems with rational or floating-point number coefficients. For systems with exact numeric nonrational coefficients, only the Loos-Weispfenning algorithm is implemented. specifies whether the Loos-Weispfenning algorithm is available. specifies whether the simplex and revised simplex algorithms can be used. determines which method is used if all are available and applicable. The value of the option should be a triple . For linear systems with up to variables, Mathematica uses the Loos-Weispfenning method [15]; for systems with to variables, the simplex algorithm; and for more than variables, the revised simplex algorithm. If the simplex algorithm is used, the slack variables are used if the number of inequalities is no more than times the number of variables and either is True or is Automatic and the system is exact. The default values are , , , and s==Automatic.

By default, the simplex algorithm is used to find a solution of a linear system with three variables.
In[153]:=
Click for copyable input
Out[153]=
Here the revised simplex algorithm is used.
In[154]:=
Click for copyable input
Out[155]=
Here the Loos-Weispfenning algorithm is used.
In[156]:=
Click for copyable input
Out[157]=
In[158]:=
Click for copyable input
Here the Loos-Weispfenning algorithm is used because the simplex and revised simplex algorithms are not implemented for systems with exact nonrational coefficients.
In[159]:=
Click for copyable input
Out[159]=
With set to False, and simplex and revised simplex not applicable, FindInstance has to use the CAD algorithm here.
In[160]:=
Click for copyable input
Out[161]=
In[162]:=
Click for copyable input

LinearEquations

The option specifies whether linear equation constraints with constant leading coefficients should be used to eliminate variables. This generally improves the performance of the algorithm. The option is provided to allow experimentation with the "pure" CAD-based decision algorithm.

Here Mathematica uses the first equation to eliminate before using CAD to find a solution of the resulting system with two variables.
In[163]:=
Click for copyable input
Out[163]=
Here Mathematica uses CAD to find a solution of the original system with three variables.
In[164]:=
Click for copyable input
Out[165]=
In[166]:=
Click for copyable input

LinearQE

The option specifies methods used to handle systems containing at least one innermost quantifier variable that appears at most linearly in all equations and inequalities in the system. The option setting does not affect solving of decision problems. With the default setting True, Mathematica uses the Loos-Weispfenning algorithm [15] to eliminate all quantifier variables that appear only linearly in the system, and then if there are any quantifiers left or the result needs to be solved for the free variables, the CAD algorithm is used. With LinearQE->Automatic, the Loos-Weispfenning algorithm is used only for variables that appear in the system only linearly with constant coefficients. With LinearQE->False, the Loos-Weispfenning algorithm is not used.

With the default setting LinearQE->True, the Loos-Weispfenning algorithm is used to eliminate both and , and CAD is used to solve the remaining quantifier-free system with two variables.
In[167]:=
Click for copyable input
Out[167]=
With LinearQE->Automatic, the Loos-Weispfenning algorithm is used only to eliminate , and CAD is used to solve the remaining system with three variables. For this example, the default method is much faster.
In[168]:=
Click for copyable input
Out[169]=
With LinearQE->False, the Loos-Weispfenning algorithm is not used. Reduce uses CAD to solve the original system with four variables, which for this example takes much longer.
In[170]:=
Click for copyable input
Out[171]=
All three methods give the same answer.
In[172]:=
Click for copyable input
Out[172]=
Here is an example where the default method is not the fastest. With the default setting LinearQE->True, the Loos-Weispfenning algorithm is used to eliminate both and , and CAD is used to solve the remaining system with one quantified and one free variable.
In[173]:=
Click for copyable input
Out[174]=
With LinearQE->Automatic, the Loos-Weispfenning algorithm is used only to eliminate , and then CAD is used to solve the remaining system with two quantified variables and one free variable.
In[175]:=
Click for copyable input
Out[176]=
With LinearQE->False, the CAD algorithm is used to solve the system. This is the fastest method for this example.
In[177]:=
Click for copyable input
Out[178]=
The default setting LinearQE->True is definitely advantageous for quantifier elimination problems where all quantified variables appear only linearly in the system and the quantifier-free version of the system does not need to be given in a solved form. This is because the complexity of the Loos-Weispfenning algorithm depends very little on the number of free variables, unlike the complexity of the CAD algorithm that is doubly exponential in the number of all variables. With LinearQE->False and QuadraticQE->False, this example does not finish in 1000 seconds.
In[179]:=
Click for copyable input
Out[180]=

LWPreprocessor

The option setting affects solving decision problems and instance finding. The option specifies whether the Loos-Weispfenning algorithm [8] should be used to eliminate variables that appear at most linearly in all equations and inequalities before applying the CAD algorithm to the resulting system. With the default setting Automatic, Mathematica uses the Loos-Weispfenning algorithm to eliminate variables that appear only linearly with constant coefficients. With LWPreprocessor->True, the Loos-Weispfenning algorithm is used for all variables that appear only linearly. With LWPreprocessor->False, the Loos-Weispfenning algorithm is not used as a preprocessor to the CAD-based decision algorithm.

With the default setting LWPreprocessor->Automatic, the Loos-Weispfenning algorithm is used only to eliminate , and CAD is used to find a solution of the remaining system with three variables.
In[181]:=
Click for copyable input
Out[181]=
With LWPreprocessor->True, the Loos-Weispfenning algorithm is used to eliminate both and , and CAD is used to find a solution of the remaining system with two variables. For this example, this method is slower than the default one.
In[182]:=
Click for copyable input
Out[183]=
With LWPreprocessor->False, the CAD algorithm is used to find a solution of the original system with four variables. For this example, this method is as fast as the default.
In[184]:=
Click for copyable input
Out[185]=
This example differs from the previous one only in that the last inequality was turned into an equation. With the default setting LWPreprocessor->Automatic, the Loos-Weispfenning algorithm is only used to eliminate , and CAD is used to find a solution of the remaining system with three variables.
In[186]:=
Click for copyable input
Out[187]=
With LWPreprocessor->True, the Loos-Weispfenning algorithm is used to eliminate both and , and CAD is used to find a solution of the remaining system with two variables. For the revised example, this method is faster than the default one.
In[188]:=
Click for copyable input
Out[189]=
With LWPreprocessor->False, the CAD algorithm is used to find a solution of the original system with four variables. For the revised example, this is seven times slower than the default method.
In[190]:=
Click for copyable input
Out[191]=
In[192]:=
Click for copyable input

ProjectAlgebraic

The setting of the option affects handling of algebraic number coefficients in the CAD algorithm.

Algebraic numbers found in coefficients of the input system are replaced with new variables. The new variables are always put first in the variable ordering so that in the projection phase of the CAD algorithm they are eliminated last. When the current projection polynomials contain variables with at least first variables replacing algebraic number coefficients, we have a choice of whether or not to continue the projection phase. If we do not continue the projection phase, we can start the lifting phase extending the zero-dimensional cell in the first variables on which each of the variables is equal to the corresponding algebraic number coefficient. If we choose to compute the last projections, we may find in the lifting phase that the algebraic number coefficient corresponding to a variable being lifted lies between the roots of the projection polynomials. Hence for this variable we will be extending a one-dimensional cell with a rational number sample point. Thus there is a trade-off between avoiding computation of the last projections and avoiding algebraic number coordinates in sample points.

With ProjectAlgebraic->True, the projection phase is continued for variables replacing algebraic number coefficients until there is one variable left. With ProjectAlgebraic->False, the projection phase is stopped as soon as there is one variable left that does not replace an algebraic number coefficient. With the default setting ProjectAlgebraic->Automatic, the projection phase is stopped if there is at most one variable left that does not replace an algebraic number coefficient and there are at least three projection polynomials, or there is a projection polynomial of degree more than two in the projection variable.

With few equations and inequalities in the system and few high-degree algebraic number coefficients, ProjectAlgebraics->True tends to be a better choice. (N is applied to the output for better readability.)
In[193]:=
Click for copyable input
Out[196]=
In[197]:=
Click for copyable input
Out[198]=
With many low-degree algebraic number coefficients, equations, and inequalities in the system, ProjectAlgebraics->False tends to be faster.
In[199]:=
Click for copyable input
Out[200]=
In[201]:=
Click for copyable input
Out[202]=
In[203]:=
Click for copyable input

ProveMultiplicities

The setting of determines the way in which the lifting phase of the CAD algorithm validates multiple roots and zero leading coefficients of projection polynomials obtained using arbitrary-precision floating-point number (Mathematica "bignum") computations (for more details, see [14, 24]). With the default setting ProveMultiplicities->True, Mathematica uses information about the origins of the cell, if this is not sufficient computes exact values of cell coordinates and uses principal subresultant coefficients and exact zero testing, and only if this fails reverts to exact computations. With ProveMultiplicities->Automatic, Mathematica uses information about the origins of the cell and, if this is not sufficient, reverts to exact computation. With ProveMultiplicities->False, Mathematica reverts to exact computation each time bignum computations fail to separate all roots or prove that the leading coefficients of projection polynomials are nonzero.

Generally, using all available methods of validating results obtained with arbitrary-precision floating-point number computations leads to better performance.
In[204]:=
Click for copyable input
Out[205]=
In[206]:=
Click for copyable input
Out[207]=
In[208]:=
Click for copyable input
Out[209]=
In[210]:=
Click for copyable input

QuadraticQE

The option specifies whether the quadratic case of Weispfenning's quantifier elimination by virtual substitution algorithm [22, 23] should be used to eliminate quantified variables that appear at most quadratically in all equations and inequalities in the system. The complexity of Weispfenning's algorithm depends very little on the number of free variables, unlike the complexity of the CAD algorithm that is doubly exponential in the number of all variables. Hence, it is definitely advantageous to use it when all quantifiers can be eliminated using the algorithm, there are many free variables present, and the quantifier-free version of the system does not need to be given in a solved form. On the other hand, eliminating a variable using Weispfenning's algorithm often significantly increases the size of the formula. So if Mathematica needs to apply CAD to the result or if the system contains few free variables, using CAD on the original system may be faster. With the default setting Automatic, Mathematica uses the algorithm for Resolve with no variables specified and with at least two parameters present, and for Reduce and Resolve with at least three variables as long as elimination of one variable at most doubles the LeafCount of the system. This criterion seems to work reasonably well; however, for some examples it does not give the optimal choice of the algorithm. Changing the option value may allow problems to be solved which otherwise take a very long time. With QuadraticQE->True, Weispfenning's algorithm is used whenever there is a quadratic variable to eliminate, with QuardaticQE->False, Weispfenning's algorithm is not used.

Resolve with no variables specified and with at least two parameters present uses Weispfenning's algorithm to eliminate . The result is not solved for the parameters , , and .
In[211]:=
Click for copyable input
Out[211]=
Reduce by default uses CAD for this example. The result is solved for the parameters , , and .
In[212]:=
Click for copyable input
Out[212]=
With QuadraticQE->True, Reduce uses Weispfenning's algorithm to eliminate and then CAD to solve the quantifier-free formula for the parameters , , and . In this example this is faster than the default method of using CAD from the beginning.
In[213]:=
Click for copyable input
Out[214]=
For this system with three free variables, Weispfenning's algorithm is much faster than CAD.
In[215]:=
Click for copyable input
Out[216]=
In[217]:=
Click for copyable input
Out[218]=
For this system with only one free variable Resolve uses CAD.
In[219]:=
Click for copyable input
Out[219]=
Weispfenning's algorithm takes somewhat more time and gives a more complicated result.
In[220]:=
Click for copyable input
Out[221]=
In[222]:=
Click for copyable input

QVSPreprocessor

The option setting affects solving decision problems and instance finding. The option specifies whether the quadratic case of Weispfenning's quantifier elimination by virtual substitution algorithm [22, 23] should be used to eliminate variables that appear at most quadratically in all equations and inequalities before applying the CAD algorithm to the resulting system. The default setting is False and the algorithm is not used. There are examples where using Weispfenning's algorithm as a preprocessor significantly helps the performance, and there are examples where using the preprocessor significantly hurts the performance. It seems that the preprocessor tends to help in examples with many variables and where instances exist. With QVSPreprocessor->True, Weispfenning's algorithm is used each time there is a quadratic variable. With QVSPreprocessor->Automatic, Mathematica uses the algorithm for systems with at least four variables.

Here Mathematica finds a solution using Weispfenning's algorithm as a preprocessor. Without the preprocessor, this example takes much longer.
In[223]:=
Click for copyable input
Out[224]=
In[225]:=
Click for copyable input
Out[226]=
For this example, using CAD without the preprocessor is faster.
In[227]:=
Click for copyable input
Out[228]=
In[229]:=
Click for copyable input
Out[230]=

ReducePowers

For any variable in the input to the CAD algorithm, if all powers of appearing in the system are integer multiples of an integer , Mathematica replaces in the input system with a new variable, runs the CAD on the new system, and then resolves the answer so that it is expressed in terms of the original variables. Setting ReducePowers->False turns off this shortcut. With ReducePowers->False, the algebraic functions appearing as cell bounds in the output of the CAD algorithm are always rational functions, quadratic radical expressions, or Root objects. With the default setting ReducePowers->True, they may in addition be for any of the previous expressions , or Root[a#n-e&, 1] for some integer , and a rational function or a quadratic radical expression .

With the default setting ReducePowers->True, the CAD algorithm solves a quadratic equation in variables replacing and , and then the result is represented in terms of and . The result contains Root objects with quadratic radical expressions inside.
In[231]:=
Click for copyable input
Out[231]=
With ReducePowers->True, the CAD algorithm solves the original 50^(th)-degree equation that takes several times longer. The result contains only Root objects with polynomial expressions inside.
In[232]:=
Click for copyable input
Out[233]=

RootReduced

For systems with equational constraints generating a zero-dimensional ideal , Mathematica 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 solutions are easily represented as polynomials in the last coordinate. Otherwise the coordinates are given as Root objects representing algebraic numbers defined by triangular systems of equations. Setting to True causes Mathematica to represent each coordinate as a single numeric Root object defined by a minimal polynomial and a root number. Computing this reduced representation often takes much longer than solving the system.

By default, we get the value of expressed in terms of .
In[234]:=
Click for copyable input
Out[234]=
With Backsubstitution->True, we get a numeric value of given in the AlgebraicNumber representation.
In[235]:=
Click for copyable input
Out[235]=
Setting RootReduced->True causes Mathematica to represent the value of as a single Root object. However, the computation takes more time.
In[236]:=
Click for copyable input
Out[237]=
In[238]:=
Click for copyable input
By default, Reduce expresses the solution in terms of Root objects representing algebraic numbers defined by triangular systems of equations.
In[239]:=
Click for copyable input
Out[239]=
Setting RootReduced->True causes Mathematica to represent the value of as a Root object defined by a minimal polynomial and a root number. However, the computation takes more time.
In[240]:=
Click for copyable input
Out[241]=
In[242]:=
Click for copyable input

SimplifyInequalities

With the default setting SimplifyInequalities->Automatic, Mathematica uses the inequality simplification heuristic presented in [25] to simplify inputs to the CAD algorithm, deduce inequalities on CAD projection factors, and use the inequalities to recognize nonzero coefficients and subresultants in the projection phase and to eliminate cells in the lifting phase. The heuristic is also used to simplify intermediate results in the virtual substitution algorithms [15, 23]. Setting SimplifyInequalities to True makes the inequality simplification heuristic perform an additional transformation . With SimplifyInequalities->False, the inequality simplification heuristic is not used.

In this example inequality simplification makes the CAD computation faster.
In[243]:=
Click for copyable input
Out[243]=
In[244]:=
Click for copyable input
Out[245]=
In the first example equation, factoring makes the CAD computation faster; in the second example, it makes the CAD computation slower.
In[246]:=
Click for copyable input
Out[250]=
In[251]:=
Click for copyable input
Out[252]=

ThreadOr

The option specifies how the identity

should be used in the decision algorithm (Reduce and Resolve for systems containing no free variables or parameters), FindInstance, and quantifier elimination (Resolve with no variables specified). With the default setting ThreadOr->True, the identity (8) is used before attempting any solution algorithms. With ThreadOr->False, the identity (8) may be used by algorithms that require using it (for instance, the simplex algorithm), but will not be used by algorithms that do not require using it (for instance, the CAD algorithm).

Here Reduce finds an instance satisfying the first simpler term of Or, and hence avoids dealing with the second, more complicated, term.
In[253]:=
Click for copyable input
Out[253]=
With ThreadOr->False, Reduce needs to run a CAD-based decision algorithm on the whole system.
In[254]:=
Click for copyable input
Out[255]=
This system has no solutions and so with ThreadOr->True, Reduce needs to run a CAD-based decision algorithm on each of the terms.
In[256]:=
Click for copyable input
Out[257]=
Since all six terms of Or involve exactly the same polynomials, running a CAD-based decision algorithm on the whole expression consists of very similar computations as running a CAD-based decision algorithm on one of the terms. In this case the computation with ThreadOr->False is faster.
In[258]:=
Click for copyable input
Out[259]=
In[260]:=
Click for copyable input

ZengDecision

The option specifies whether Mathematica should use the algorithm by G. X. Zeng and X. N. Zeng [18]. The algorithm applies to decision problems with systems that consist of a single strict inequality. There are examples for which the algorithm performs better than the strict inequality variant of the CAD algorithm described in [13]. However, for randomly chosen inequalities, it seems to perform worse; therefore, it is not used by default. Here is an example from [18] that runs slightly faster with ZengDecision->True.
In[261]:=
Click for copyable input
Out[261]=
In[262]:=
Click for copyable input
Out[263]=
In[264]:=
Click for copyable input

References

[1] Caviness B. F. and J. R. Johnson, eds. Quantifier Elimination and Cylindrical Algebraic Decomposition: Texts and Monographs in Symbolic Computation. Springer-Verlag (1998)

[2] Tarski A. A Decision Method for Elementary Algebra and Geometry. University of California Press (1951)

[3] Łojasiewicz S. Ensembles Semi-Analytiques. Inst. Hautes Études Sci. (1964)

[4] Collins G. E. "Quantifier Elimination for the Elementary Theory of Real Closed Fields by Cylindrical Algebraic Decomposition" Lecture Notes in Computer Science 33 (1975): 134-183

[5] Hong H. "An Improvement of the Projection Operator in Cylindrical Algebraic Decomposition" In Issac '90: Proceedings of the International Symposium on Symbolic and Algebraic Computation (M. Nagata, ed.), 261-264, 1990

[6] McCallum S. "An Improved Projection for Cylindrical Algebraic Decomposition of Three Dimensional Space" J. Symb. Comput. 5, no. 1/2 (1988): 141-161

[7] McCallum S. "An Improved Projection for Cylindrical Algebraic Decomposition" In Quantifier Elimination and Cylindrical Algebraic Decomposition: Texts and Monographs in Symbolic Computation (B. F. Caviness and J. R. Johnson, eds.). Springer-Verlag, 242-268, 1998

[8] Brown C. W. "Improved Projection for Cylindrical Algebraic Decomposition" J. Symb. Comput. 32, no. 5 (2001): 447-465

[9] Collins G. E. "Quantifier Elimination by Cylindrical Algebraic Decomposition—Twenty Years of Progress" In Quantifier Elimination and Cylindrical Algebraic Decomposition: Texts and Monographs in Symbolic Computation (B. F. Caviness and J. R. Johnson, eds.). Springer-Verlag, 8-23, 1998

[10] McCallum S. "On Projection in CAD-Based Quantifier Elimination with Equational Constraint" In Issac '99: Proceedings of the International Symposium on Symbolic and Algebraic Computation (Sam Dooley, ed.), 145-149, 1999

[11] McCallum S. "On Propagation of Equational Constraints in CAD-Based Quantifier Elimination" In Issac 2001: Proceedings of the International Symposium on Symbolic and Algebraic Computation, 223-231, 2001

[12] Strzebonski A. "An Algorithm for Systems of Strong Polynomial Inequalities" The Mathematica Journal 4, no. 4 (1994): 74-77

[13] Strzebonski A. "Solving Systems of Strict Polynomial Inequalities" J. Symb. Comput. 29, no. 3 (2000): 471-480

[14] Strzebonski A. "Cylindrical Algebraic Decomposition Using Validated Numerics" Paper presented at the ACA 2002 Session on Symbolic-Numerical Methods in Computational Science, Volos, Greece (2002) (Notebook with the conference talk available at members.wolfram.com/adams)

[15] Loos R. and V. Weispfenning. "Applying Linear Quantifier Elimination" Comput. J. 36, no. 5 (1993): 450-461

[16] Strzebonski A. "A Real Polynomial Decision Algorithm Using Arbitrary-Precision Floating Point Arithmetic" Reliable Comput. 5, no. 3 (1999): 337-346; Developments in Reliable Computing (Tibor Csendes, ed.). Kluwer Academic Publishers (1999): 337-346

[17] Aubry P., F. Rouillier, and M. Safey El Din. "Real Solving for Positive Dimensional Systems" J. Symb. Comput. 34, no. 6 (2002): 543-560

[18] Zeng G. X. and X. N. Zeng. "An Effective Decision Method for Semidefinite Polynomials" J. Symb. Comput. 37, no. 1 (2004): 83-99

[19] Akritas A. G. and A. Strzebonski. "A Comparative Study of Two Real Root Isolation Methods" Nonlinear Analysis: Modelling and Control 10, no. 4 (2005): 297-304

[20] Faugere J. C., P. Gianni, D. Lazard, and T. Mora. "Efficient Computation of Zero-Dimensional Gröbner Bases by Change of Ordering" J. Symb. Comput. 16, no. 4 (1993): 329-344

[21] Dorato P., W. Yang, and C. Abdallah. "Robust Multi-Objective Feedback Design by Quantifier Elimination" J. Symb. Comput. 24, no. 2 (1997): 153-159

[22] Weispfenning V. "Quantifier Elimination for Real Algebra—The Cubic Case" In Issac 1994: Proceedings of the International Symposium on Symbolic and Algebraic Computation, 258-263, 1994

[23] Weispfenning V. "Quantifier Elimination for Real Algebra—The Quadratic Case and Beyond" Appl. Algebra Eng. Commun. Comput. 8, no. 2 (1997): 85-101

[24] Strzebonski A. "Cylindrical Algebraic Decomposition Using Validated Numerics" J. Symb. Comput. 41, no. 9 (2006): 1021-1038

[25] Brown C. W. and A. Strzebonski. "Black-Box/White-Box Simplification and Applications to Quantifier Elimination" In Issac 2010: Proceedings of the International Symposium on Symbolic and Algebraic Computation (Stephen M. Watt, ed.), 69-76, 2010

[26] Strzebonski A. "Computation with Semialgebraic Sets Represented by Cylindrical Algebraic Formulas" In Issac 2010: Proceedings of the International Symposium on Symbolic and Algebraic Computation (Stephen M. Watt, ed.), 61-68, 2010

[27] Strzebonski A. "Solving Polynomial Systems over Semialgebraic Sets Represented by Cylindrical Algebraic Formulas" In Issac 2012: Proceedings of the International Symposium on Symbolic and Algebraic Computation (Joris van der Hoeven and Mark van Hoeij, eds.), 335-342, 2012

New to Mathematica? Find your learning path »
Have a question? Ask support »