compute all the solutions of a semi-algebraic system
compute the solutions of a semi-algebraic system interactively
compute sample points for a semi-algebraic system
RealTriangularize(sys, R, options)
RealTriangularize(F, N, P, H, R, options)
LazyRealTriangularize(sys, R, options)
LazyRealTriangularize(F, N, P, H, R, options)
SamplePoints(sys, R, options)
SamplePoints(F, N, P, H, R, options)
list of polynomial equations, inequations, and inequalities over R
list of polynomials over R representing equations
list of polynomials over R representing non-negativity conditions
list of polynomials over R representing positivity conditions
list of polynomials over R representing inequations
object of type cadcell
(optional) equation of the form 'output'=format, where format is either 'piecewise', 'record', 'list' , 'zerodimensional', or equation of the form 'isolation'='algorithm', where 'algorithm'='Discoverer' or 'algorithm'='VincentCollinsAkritas' , or equation of the form 'method'='algorithm', where 'algorithm'='recursive' or 'algorithm'='incremental' , or equation of the form 'relaxation'=algorithm, where 'algorithm'='explicit' or 'algorithm'='implicit' .
The output option controls the form of the output.
If 'output'='list' is specified, the output is a list of objects of type regular_semi_algebraic_system, for RealTriangularize and LazyRealTriangularize, and a list of objects of type box, for SamplePoints. This is the default for RealTriangularize and for SamplePoints.
If 'output'='piecewise' is specified, then the output format is a case discussion tree encoded by a piecewise object. This is not a valid option for SamplePoints, and it is the default for LazyRealTriangularize.
If 'output'='record' is specified, then the output is a sequence of Maple records.
If 'output'='zerodimensional' is specified, then the output is a list of regular semi-algebraic sets. (See SemiAlgebraicSetTools for the definition of a regular semi-algebraic system.) The usage of this format is restricted to the case where the constructible set associated to S has finitely many solutions. This condition holds in particular when the semi-algebraic system S itself has finitely many solutions.
The isolation option controls the method used for isolating the real roots of a zero-dimensional regular chain. (See RealRootIsolate for the subject of real root isolation of a regular chain.)
If 'isolation'='VincentCollinsAkritas' is specified, then the method is a generalization of the Vincent-Collins-Akritas algorithm which isolates real roots for univariate polynomials. The techniques are very close to the ones used by Renaud Rioboo in his ISSAC 1992 paper (see reference below).
If 'isolation'='Discoverer' is specified, then the method implements the algorithm of the paper "An Algorithm for Isolating the Real Solutions of Semi-algebraic Systems." by Bican Xia and Lu Yang. The default method is Discoverer.
The method option controls the decomposition algorithm.
If 'method'='recursive' is specified, then the algorithm presented in the ISSAC 2010 paper by Changbo Chen et al. (see reference below) is used.
If 'method'='incremental' is specified, then the algorithm presented in the ISSAC 2011 paper by Changbo Chen et al. (see reference below) is used. This option is the default.
The relaxation option controls the use of a relaxation technique aiming at reducing the number of components in the output. This strategy is described in the ISSAC 2011 paper by Changbo Chen et al. (see reference below).
If 'relaxation'='explicit' is specified, then criteria are used to check whether relaxation techniques apply. These criteria have some computational cost. However, relaxation techniques might speed up the decomposition process dramatically in some cases.
If 'relaxation'='implicit' is specified, then relaxation techniques are applied in a light way, at essentially no cost. However, some opportunities for relaxation can only discovered in the 'explicit' mode. The option 'relaxation'='implicit' is used by default.
Consider the semi-algebraic system S whose unknowns are the variables of R and whose equations, non-negative inequalities, strictly positive inequalities, and inequations are given either by sys or by F, N, P, and H, respectively. The solutions of S are the real numbers which satisfy simultaneously the equations, inequalities, and inequations of S.
The commands RealTriangularize(F, N, P, H, R) or RealTriangularize(sys, R) return a triangular decomposition of the solutions of S in the following sense. They compute a list of regular semi-algebraic systems such that the union of their solution sets is exactly the solution set of S. (See SemiAlgebraicSetTools for the definition of a regular semi-algebraic system.)
The commands LazyRealTriangularize(F, N, P, H, R) or LazyRealTriangularize(sys, R) return regular semi-algebraic systems and unevaluated recursive calls in a piecewise format, unless a different output format is requested. The zero sets of those regular semi-algebraic systems form a "lazy" real triangular decomposition of S in the following sense.
The zero sets of those regular semi-algebraic systems form a subset U of the solution set of S;
The dimension of the solution set of S∖U is strictly less than the dimension of the constructible set associated with S.
By evaluating the recursive calls in finitely many steps, one can eventually obtain a triangular decomposition of S.
When the option 'output'='list' is specified, the recursive calls will be discarded and only the regular semi-algebraic systems are returned as a list.
The commands SamplePoints(F, N, P, H, R) and SamplePoints(sys, R) return at least one sample point per real connected component of S.
The output format is the same as for the command RealRootIsolate. That is, a list of so-called boxes, each box containing one and only one sample point. (See SemiAlgebraicSetTools or RealRootIsolate for the definition of a box.)
The BoxValues command retrieves a detailed description of a box.
In addition, each box can be refined with an arbitrary small precision. See the commands RefineBox and RefineListBox.
The command SamplePoints(C,R) returns a sample point of the CAD cell given by C. The type cadcell encodes any CAD cell and is used for one of the output formats of the command CylindricalAlgebraicDecompose. See SemiAlgebraicSetTools for the definition of a CAD cell.
Define a ring of polynomials.
R ≔ PolynomialRing⁡x,y,z:
Define a set of equations.
F ≔ x3+y+z−1,x+y3+z−1,x+y+z3−1
Define a set of non-negative polynomials.
Define a set of positive polynomials.
Define a set of inequations.
H ≔ x
Compute the solutions of F for which x is nonzero.
dec ≔ RealTriangularize⁡F,N,P,H,R
Compute the solutions of F for which x≠1.
dec ≔ RealTriangularize⁡F,N,P,x−1,R
Compute the solutions of F for which x is negative.
dec ≔ RealTriangularize⁡F,N,−x,,R
For input systems which are known to have finitely many solutions like F, the option 'output'='zerodimensional' provides an alternative output format based on isolation boxes, as for RealRootIsolate.
dec ≔ RealTriangularize⁡F,R,output=zerodimensional
Consider the unit circle in the Euclidean plane.
R ≔ PolynomialRing⁡y,x;sys ≔ x2+y2=1
Compute its real points.
Consider the generic equation of degree two.
R ≔ PolynomialRing⁡x,c,b,a;sys ≔ a⁢x2+b⁢x+c=0
Compute a triangular decomposition of the 4-variable hypersurface it defines.
dec ≔ RealTriangularize⁡sys,R
Consider the piecewise output format.
Consider the record output format.
Use LazyRealTriangularize to start the decomposition.
dec ≔ LazyRealTriangularize⁡sys,R
Go one step further, computing components in lower dimension.
dec2 ≔ value⁡dec
Go the last step, computing components in dimension zero.
Use the list output format.
dec ≔ LazyRealTriangularize⁡sys,R,output=list
Use the record output format.
dec ≔ LazyRealTriangularize⁡sys,R,output=record
Go one step further.
Go the last step.
Consider again the unit circle in the Euclidean plane.
Compute sample points of it.
P ≔ SamplePoints⁡sys,R
Request points with positive abscissa.
sys ≔ x2+y2=1,0<x
Return to the generic equation of degree two.
Compute sample points of the 4-variable hypersurface it defines.
The relaxation option.
R ≔ PolynomialRing⁡x,a,b
sys ≔ x2+a+b⁢x+a=0,0<x−a
st ≔ time⁡:rtd0 ≔ RealTriangularize⁡sys,R:time⁡−st
st ≔ time⁡:rtd1 ≔ RealTriangularize⁡sys,R,relaxation=explicit:time⁡−st
Accessing a sample point from a CAD cell.
cad ≔ CylindricalAlgebraicDecompose⁡x2−a=0,R,output='cadcell'
cc ≔ cad1;Display⁡cc,R
F. Boulier, C. Chen, F. Lemaire, M. Moreno Maza, "Real root isolation of regular chains." ASCM'2009, Math-for-Industry, Lecture Note Series Vol. 22.
C. Chen, J. H. Davenport, J. P. May, M. Moreno Maza, B. Xia, R. Xiao, "Triangular Decomposition of Semi-algebraic Systems." Proceedings of ISSAC 2010, ACM Press, 2010.
C. Chen, J. H. Davenport, M. Moreno Maza, B. Xia, R. Xiao, "Computing with semi-algebraic sets represented by triangular decomposition". Proceedings of the 2011 International Symposium on Symbolic and Algebraic Computation (ISSAC 2011), ACM Press, pp. 75--82, 2011.
R. Rioboo, Computation of the real closure of an ordered field. Proceedings of ISSAC'92, Academic Press, San Francisco.
L. Yang, X. Hou, B. Xia, A complete algorithm for automated discovering of a class of inequality-type theorems. Sci. China Ser. F, Vol. 44 (2001): 33-49.
B. Xia, L. Yang, An Algorithm for Isolating the Real Solutions of Semi-algebraic Systems. J. Symb. Comp., Vol. 34 No. 5 (2001): 461-477.
B. Xia, T. Zhang, Real Solution Isolation Using Interval Arithmetic. Computers and Mathematics with Applications, Vol. 52 (2006): 853-860.
The RegularChains[LazyRealTriangularize] and RegularChains[SamplePoints] commands were introduced in Maple 15.
For more information on Maple 15 changes, see Updates in Maple 15.
The C parameter was introduced in Maple 16.
The and options were introduced in Maple 16.
For more information on Maple 16 changes, see Updates in Maple 16.