RegularChains[RealTriangularize]  compute all the solutions of a semialgebraic system
RegularChains[LazyRealTriangularize]  compute the solutions of a semialgebraic system interactively
RegularChains[SamplePoints]  compute sample points for a semialgebraic system

Calling Sequence


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)
SamplePoints(C, R)


Parameters


sys



list of polynomial equations, inequations, and inequalities over R

F



list of polynomials over R representing equations

N



list of polynomials over R representing nonnegativity conditions

P



list of polynomials over R representing positivity conditions

H



list of polynomials over R representing inequations

C



object of type cadcell

R



polynomial ring

options



(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' .





Options


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 semialgebraic sets. (See SemiAlgebraicSetTools for the definition of a regular semialgebraic system.) The usage of this format is restricted to the case where the constructible set associated to has finitely many solutions. This condition holds in particular when the semialgebraic system itself has finitely many solutions.

The isolation option controls the method used for isolating the real roots of a zerodimensional 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 VincentCollinsAkritas 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 Semialgebraic 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.



Description


•

The commands RealTriangularize(F, N, P, H, R) or RealTriangularize(sys, R) return a triangular decomposition of the solutions of in the following sense. They compute a list of regular semialgebraic systems such that the union of their solution sets is exactly the solution set of . (See SemiAlgebraicSetTools for the definition of a regular semialgebraic system.)

•

The commands LazyRealTriangularize(F, N, P, H, R) or LazyRealTriangularize(sys, R) return regular semialgebraic systems and unevaluated recursive calls in a piecewise format, unless a different output format is requested. The zero sets of those regular semialgebraic systems form a "lazy" real triangular decomposition of in the following sense.

–

The zero sets of those regular semialgebraic systems form a subset of the solution set of ;

–

The dimension of the solution set of is strictly less than the dimension of the constructible set associated with .

–

By evaluating the recursive calls in finitely many steps, one can eventually obtain a triangular decomposition of .


When the option 'output'='list' is specified, the recursive calls will be discarded and only the regular semialgebraic 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 .

–

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.



Compatibility


•

The RegularChains[LazyRealTriangularize] and RegularChains[SamplePoints] commands were introduced in Maple 15.

•

The C parameter was introduced in Maple 16.

•

The and options were introduced in Maple 16.



Examples


>


Define a ring of polynomials.
>


Define a set of equations.
>


 (1) 
Define a set of nonnegative polynomials.
>


 (2) 
Define a set of positive polynomials.
>


 (3) 
Define a set of inequations.
>


 (4) 
Compute the solutions of F for which is nonzero.
>


 (5) 
>


 (6) 
Compute the solutions of F for which .
>


 (7) 
>


 (8) 
Compute the solutions of F for which is negative.
>


 (9) 
>


 (10) 
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.
>


 (11) 
>


 (12) 
Consider the unit circle in the Euclidean plane.
>


 (13) 
Compute its real points.
>


 (14) 
Consider the generic equation of degree two.
>


 (15) 
Compute a triangular decomposition of the 4variable hypersurface it defines.
>


 (16) 
>


 (17) 
Consider the piecewise output format.
>


 (18) 
Consider the record output format.
>


 (19) 
Use LazyRealTriangularize to start the decomposition.
>


 (20) 
Go one step further, computing components in lower dimension.
>


 (21) 
Go the last step, computing components in dimension zero.
>


 (22) 
Use the list output format.
>


 (23) 
>


 (24) 
Use the record output format.
>


 (25) 
Go one step further.
>


 (26) 
Go the last step.
>


 (27) 
Consider again the unit circle in the Euclidean plane.
>


 (28) 
Compute sample points of it.
>


 (29) 
>


 (30) 
Request points with positive abscissa.
>


 (31) 
>


 (32) 
>


 (33) 
Return to the generic equation of degree two.
>


 (34) 
Compute sample points of the 4variable hypersurface it defines.
>


 (35) 
>


 (36) 
The relaxation option.
>


>


 (37) 
>


 (38) 
 (39) 
 (40) 
>


 (41) 
Accessing a sample point from a CAD cell.
>


 (42) 
>


 (43) 
>


 (44) 


See Also


BorderPolynomial, BoxValues, CylindricalAlgebraicDecompose, Display, RealRootClassification, RealRootIsolate, RefineBox, RefineListBox, RegularChains, SemiAlgebraicSetTools, Triangularize


References



F. Boulier, C. Chen, F. Lemaire, M. Moreno Maza, "Real root isolation of regular chains." ASCM'2009, MathforIndustry, Lecture Note Series Vol. 22.


C. Chen, J. H. Davenport, J. P. May, M. Moreno Maza, B. Xia, R. Xiao, "Triangular Decomposition of Semialgebraic Systems." Proceedings of ISSAC 2010, ACM Press, 2010.


C. Chen, J. H. Davenport, M. Moreno Maza, B. Xia, R. Xiao, "Computing with semialgebraic sets represented by triangular decomposition". Proceedings of the 2011 International Symposium on Symbolic and Algebraic Computation (ISSAC 2011), ACM Press, pp. 7582, 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 inequalitytype theorems. Sci. China Ser. F, Vol. 44 (2001): 3349.


B. Xia, L. Yang, An Algorithm for Isolating the Real Solutions of Semialgebraic Systems. J. Symb. Comp., Vol. 34 No. 5 (2001): 461477.


B. Xia, T. Zhang, Real Solution Isolation Using Interval Arithmetic. Computers and Mathematics with Applications, Vol. 52 (2006): 853860.


