compute all the solutions of a semi-algebraic system - Maple 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

RegularChains[LazyRealTriangularize] - compute the solutions of a semi-algebraic system interactively

RegularChains[SamplePoints] - compute sample points for a semi-algebraic 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 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' .

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

R:=PolynomialRingx,y,z:

Define a set of equations.

F:=x3+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.

H:=x

H:=x

(4)

Compute the solutions of F for which x is nonzero.

dec:=RealTriangularizeF,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.

dec:=RealTriangularizeF,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.

dec:=RealTriangularizeF,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.

dec:=RealTriangularizeF,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.

R:=PolynomialRingy,x;sys:=x2+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.

R:=PolynomialRingx&comma;c&comma;b&comma;a&semi;sys:=ax2&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.

dec:=RealTriangularizesys&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.

dec:=LazyRealTriangularizesys&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.

dec2:=valuedec

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.

dec:=LazyRealTriangularizesys&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.

dec:=LazyRealTriangularizesys&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.

dec2:=valuedec

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.

R:=PolynomialRingy&comma;x&semi;sys:=x2&plus;y2&equals;1

R:=polynomial_ring

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

(28)

Compute sample points of it.

P:=SamplePointssys&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.

sys:=x2&plus;y2&equals;1&comma;0<x

sys:=x2&plus;y2&equals;1&comma;0<x

(31)

P:=SamplePointssys&comma;R

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

(32)

DisplayP&comma;R

&lcub;y&equals;111128&comma;5564x&equals;12&comma;&lcub;y&equals;5564&comma;111128x&equals;12&comma;&lcub;y&equals;0x&equals;1

(33)

Return to the generic equation of degree two.

R:=PolynomialRingx&comma;c&comma;b&comma;a&semi;sys:=ax2&plus;bx&plus;c&equals;0