RegularChains - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Factorization and Solving Equations : RegularChains : RegularChains/RealTriangularize

RegularChains

  

RealTriangularize

  

compute all the solutions of a semi-algebraic system

  

LazyRealTriangularize

  

compute the solutions of a semi-algebraic system interactively

  

SamplePoints

  

compute sample points for a semi-algebraic system

 

Calling Sequence

Parameters

Options

Description

Examples

References

Compatibility

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 non-negativity 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 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.

Description

• 

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.

Examples

withRegularChains:

Define a ring of polynomials.

RPolynomialRingx,y,z:

Define a set of equations.

Fx3+y+z1,x+y3+z1,x+y+z31

F:=x3+y+z1,y3+x+z1,z3+x+y1

(1)

Define a set of non-negative polynomials.

N

N:=

(2)

Define a set of positive polynomials.

P

P:=

(3)

Define a set of inequations.

Hx

H:=x

(4)

Compute the solutions of F for which x is nonzero.

decRealTriangularizeF,N,P,H,R

dec:=regular_semi_algebraic_system,regular_semi_algebraic_system,regular_semi_algebraic_system,regular_semi_algebraic_system,regular_semi_algebraic_system

(5)

Displaydec,R

{xz=0yz=0z3+2z1=0,{x1=0y+1=0z1=0,{x+1=0y1=0z1=0,{x1=0y=0z=0,{x1=0y1=0z+1=0

(6)

Compute the solutions of F for which x1.

decRealTriangularizeF,N,P,x1,R

dec:=regular_semi_algebraic_system,regular_semi_algebraic_system,regular_semi_algebraic_system,regular_semi_algebraic_system

(7)

Displaydec,R

{xz=0yz=0z3+2z1=0,{x=0y=0z1=0,{x+1=0y1=0z1=0,{x=0y1=0z=0

(8)

Compute the solutions of F for which x is negative.

decRealTriangularizeF,N,x,,R

dec:=regular_semi_algebraic_system

(9)

Displaydec,R

{x+1=0y1=0z1=0

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

decRealTriangularizeF,R,output=zerodimensional

dec:=regular_semi_algebraic_set,regular_semi_algebraic_set,regular_semi_algebraic_set,regular_semi_algebraic_set,regular_semi_algebraic_set,regular_semi_algebraic_set,regular_semi_algebraic_set

(11)

mapDisplay,dec,R

{x=38,12y=38,12z=2964,117256,{x=1y=1z=1,{x=0y=1z=0,{x=0y=0z=1,{x=1y=1z=1,{x=1y=1z=1,{x=1y=0z=0

(12)

Consider the unit circle in the Euclidean plane.

RPolynomialRingy,x;sysx2+y2=1

R:=polynomial_ring

sys:=x2+y2=1

(13)

Compute its real points.

RealTriangularizesys,R,output=record

&lcub;y2+x21=0x<1x+1>0&comma;&lcub;y=0x1=0&comma;&lcub;y=0x+1=0

(14)

Consider the generic equation of degree two.

RPolynomialRingx&comma;c&comma;b&comma;a&semi;sysax2&plus;bx&plus;c&equals;0

R:=polynomial_ring

sys:=ax2&plus;bx&plus;c&equals;0

(15)

Compute a triangular decomposition of the 4-variable hypersurface it defines.

decRealTriangularizesys&comma;R

dec:=regular_semi_algebraic_system&comma;regular_semi_algebraic_system&comma;regular_semi_algebraic_system&comma;regular_semi_algebraic_system

(16)

Displaydec&comma;R

&lcub;ax2+bx+c=04ca+b2>0anda0&comma;&lcub;2ax+b=04acb2=0a0&comma;&lcub;bx+c=0a=0b0&comma;&lcub;c=0b=0a=0

(17)

Consider the piecewise output format.

RealTriangularizesys&comma;R&comma;output&equals;piecewise

&lcub;x2a&plus;xb&plus;c&equals;0And0<4ac&plus;b2&comma;a0&lcub;xb&plus;c&equals;0&comma;a&equals;0b0c&equals;0&comma;b&equals;0&comma;a&equals;0b&equals;0a&equals;0&lcub;2ax&plus;b&equals;0&comma;4acb2&equals;0a0c&equals;0&comma;b&equals;0&comma;a&equals;0a&equals;04ac&plus;b2&equals;0otherwise

(18)

Consider the record output format.

RealTriangularizesys&comma;R&comma;output&equals;record

&lcub;ax2+bx+c=04ca+b2>0a0&comma;&lcub;2ax+b=04acb2=0a0&comma;&lcub;bx+c=0b0a=0&comma;&lcub;c=0b=0a=0

(19)

Use LazyRealTriangularize to start the decomposition.

decLazyRealTriangularizesys&comma;R

dec:=&lcub;ax2&plus;bx&plus;c&equals;0And0<4ac&plus;b2&comma;a0%LazyRealTriangularizea&equals;0&comma;ax2&plus;bx&plus;c&equals;0&comma;polynomial_ringa&equals;0%LazyRealTriangularize4ac&plus;b2&equals;0&comma;ax2&plus;bx&plus;c&equals;0&comma;polynomial_ring4ac&plus;b2&equals;0otherwise

(20)

Go one step further, computing components in lower dimension.

dec2valuedec

dec2:=&lcub;x2a&plus;xb&plus;c&equals;0And0<4ac&plus;b2&comma;a0&lcub;xb&plus;c&equals;0&comma;a&equals;0b0%LazyRealTriangularizea&equals;0&comma;b&equals;0&comma;xb&plus;c&equals;0&comma;x2a&plus;xb&plus;c&equals;0&comma;polynomial_ringb&equals;0a&equals;0&lcub;2ax&plus;b&equals;0&comma;4acb2&equals;0a0%LazyRealTriangularizea&equals;0&comma;4ac&plus;b2&equals;0&comma;4acb2&equals;0&comma;2ax&plus;b&equals;0&comma;x2a&plus;xb&plus;c&equals;0&comma;polynomial_ringa&equals;04ac&plus;b2&equals;0otherwise

(21)

Go the last step, computing components in dimension zero.

valuedec2

&lcub;x2a&plus;xb&plus;c&equals;0And0<4ac&plus;b2&comma;a0&lcub;xb&plus;c&equals;0&comma;a&equals;0b0c&equals;0&comma;b&equals;0&comma;a&equals;0b&equals;0a&equals;0&lcub;2ax&plus;b&equals;0&comma;4acb2&equals;0a0c&equals;0&comma;b&equals;0&comma;a&equals;0a&equals;04ac&plus;b2&equals;0otherwise

(22)

Use the list output format.

decLazyRealTriangularizesys&comma;R&comma;output&equals;list

dec:=regular_semi_algebraic_system

(23)

Displaydec&comma;R

&lcub;ax2+bx+c=04ca+b2>0anda0

(24)

Use the record output format.

decLazyRealTriangularizesys&comma;R&comma;output&equals;record

dec:=&lcub;ax2+bx+c=04ca+b2>0a0&comma;%LazyRealTriangularizea&equals;0&comma;ax2&plus;bx&plus;c&equals;0&comma;polynomial_ring&comma;output&equals;record&comma;%LazyRealTriangularize4ac&plus;b2&equals;0&comma;ax2&plus;bx&plus;c&equals;0&comma;polynomial_ring&comma;output&equals;record

(25)

Go one step further.

dec2valuedec

dec2:=&lcub;ax2+bx+c=04ca+b2>0a0&comma;&lcub;bx+c=0b0a=0&comma;%LazyRealTriangularizea&equals;0&comma;b&equals;0&comma;bx&plus;c&equals;0&comma;ax2&plus;bx&plus;c&equals;0&comma;polynomial_ring&comma;output&equals;record&comma;&lcub;2ax+b=04acb2=0a0&comma;%LazyRealTriangularizea&equals;0&comma;4ac&plus;b2&equals;0&comma;4acb2&equals;0&comma;2ax&plus;b&equals;0&comma;ax2&plus;bx&plus;c&equals;0&comma;polynomial_ring&comma;output&equals;record

(26)

Go the last step.

valuedec2

&lcub;ax2+bx+c=04ac+b2>0a0&comma;&lcub;bx+c=0b0a=0&comma;&lcub;c=0b=0a=0&comma;&lcub;2ax+b=04acb2=0a0&comma;&lcub;c=0b=0a=0

(27)

Consider again the unit circle in the Euclidean plane.

RPolynomialRingy&comma;x&semi;sysx2&plus;y2&equals;1

R:=polynomial_ring

sys:=x2&plus;y2&equals;1

(28)

Compute sample points of it.

PSamplePointssys&comma;R

P:=box&comma;box&comma;box&comma;box

(29)

DisplayP&comma;R

&lcub;y&equals;1x&equals;0&comma;&lcub;y&equals;1x&equals;0&comma;&lcub;y&equals;0x&equals;1&comma;&lcub;y&equals;0x&equals;1

(30)

Request points with positive abscissa.

sysx2&plus;y2&equals;1&comma;0<x

sys:=x2&plus;y2&equals;1