RegularChains[SemiAlgebraicSetTools] - Maple Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Factorization and Solving Equations : RegularChains : SemiAlgebraicSetTools Subpackage : RegularChains/SemiAlgebraicSetTools/CylindricalAlgebraicDecompose

RegularChains[SemiAlgebraicSetTools]

  

CylindricalAlgebraicDecompose

  

compute an F-invariant cylindrical algebraic decomposition

 

Calling Sequence

Parameters

Description

Examples

Compatibility

Calling Sequence

CylindricalAlgebraicDecompose(F, R)

CylindricalAlgebraicDecompose(F, R, 'output'='piecewise')

CylindricalAlgebraicDecompose(F, R, 'output'='tree')

CylindricalAlgebraicDecompose(F, R, 'output'='list')

CylindricalAlgebraicDecompose(F, R, 'output'='cadcell')

CylindricalAlgebraicDecompose(F, R, 'output'='rootof')

CylindricalAlgebraicDecompose(lsas, R, 'output'='cadcell')

CylindricalAlgebraicDecompose(lsas, R, 'output'='rootof')

Parameters

F

-

list of polynomials of R

R

-

polynomial ring

lsas

-

list of semi-algebraic systems of R

'output'='piecewise'

-

(optional) boolean flag

'output'='tree'

-

(optional) boolean flag

'output'='list'

-

(optional) boolean flag

'output'='cadcell'

-

(optional) boolean flag

'output'='rootof'

-

(optional) boolean flag

Description

• 

CylindricalAlgebraicDecompose(F, R) returns an F-invariant cylindrical algebraic decomposition of the n-dimensional real space, where n is the number of variables in R. This assumes that R has characteristic zero and no parameters, such that the base field of R is the field of rational numbers.

• 

A cylindrical algebraic decomposition (CAD) of the n-dimensional real space is a partition of the whole space into connected semi-algebraic subsets such that the cells in the partition are cylindrically arranged, that is, the projection of any two cells onto any lower dimensional real space is either equal or disjoint. This decomposition is called F-invariant if for any given cell, the sign of each polynomial in F does not change over the cell.

• 

The output of CylindricalAlgebraicDecompose(F, R) has several possible formats controlled by the options 'output'='piecewise', 'output'='tree', 'output'='list' , 'output'='cadcell' and 'output'='rootof'.

  

In all formats, each cell provides at least two pieces of information, the index of the cell and a sample point of the cell.

  

In the 'output'='cadcell' and 'output'='rootof' formats, a defining semi-algebraic system (called a Tarski Formula) is also provided.

  

Due to the cylindicity property, cells can be organized in a hierarchical manner. This is the purpose of 'output'='piecewise' and 'output'='tree', whereas the other three formats are flat representations.

  

Due to the potentially large number of cells, the 'output'='cadcell' format only shows the name cadcell for each cell in the decomposition. However, cadcell is a type and an object of that type can be passed to Display. It can also be passed to SamplePoints in order to access the sample point of the cell.

  

The 'output'='rootof' format is meant to be compatible with the output format of the solve command.

• 

For the commands CylindricalAlgebraicDecompose(lsas, R, output=cadcell) and CylindricalAlgebraicDecompose(lsas, R, output=rootof) , the input parameter lsas is a list of semi-algebraic systems. Each of these is a list of polynomial equations, inequations or inequalities given by polynomials of R. If R has n variables, a point in the n-dimensional real space satisfies such a semi-algebraic system if and only this point satisfies all the equations, inequations or inequalities of that system simultaneously.

• 

The commands CylindricalAlgebraicDecompose(lsas, R, output=cadcell) and CylindricalAlgebraicDecompose(lsas, R, output=rootof) compute a cylindrical algebraic decomposition of all the input polynomials occurring in lsas and return only the cells satisfying at least one of the input semi-algebraic systems.

• 

For these two commands, the specification of 'output'='cadcell' and 'output'='rootof' is as above.

• 

For mathematical definitions of the types squarefree_semi_algebraic_system, semi_algebraic_set and cad_cell, see the page SemiAlgebraicSetTools.

• 

Variable orders play a crucial role in the efficiency of CAD computation. The command SuggestVariableOrder computes such orders heuristically.

Examples

withRegularChains:

withChainTools:

withSemiAlgebraicSetTools:

Define a ring of polynomials.

RPolynomialRingy,x

R:=polynomial_ring

(1)

Define a set of equations.

Fxy1

F:=xy1

(2)

Compute an F-invariant cylindrical algebraic decomposition of the plane.

cadCylindricalAlgebraicDecomposeF,R

cad:=&lcub;&lcub;regular_chain&comma;1&comma;1&comma;2&comma;2y<1xregular_chain&comma;1&comma;1&comma;1&comma;1y&equals;1xregular_chain&comma;1&comma;1&comma;0&comma;01x<yx<0regular_chain&comma;0&comma;0&comma;0&comma;0x&equals;0&lcub;regular_chain&comma;1&comma;1&comma;0&comma;0y<1xregular_chain&comma;1&comma;1&comma;1&comma;1y&equals;1xregular_chain&comma;1&comma;1&comma;2&comma;21x<y0<x

(3)

The output CAD is described by a nested piecewise function. The outmost piecewise function is a function with three conditions x<0, x&equals;0, and 0<x. Each of the conditions has a corresponding expression, which is again a piecewise function. The output could be read from top to bottom and from right to left. The other two formats are shown below.

cadCylindricalAlgebraicDecomposeF&comma;R&comma;output&equals;tree

cad:=1&comma;1&comma;x&comma;1&comma;regular_chain&comma;1&comma;1&comma;1&comma;yx1&comma;1&comma;regular_chain&comma;1&comma;1&comma;2&comma;2&comma;yx1&comma;1&comma;regular_chain&comma;1&comma;1&comma;1&comma;1&comma;1&comma;yx1&comma;1&comma;regular_chain&comma;1&comma;1&comma;0&comma;0&comma;x&comma;1&comma;regular_chain&comma;0&comma;0&comma;1&comma;regular_chain&comma;0&comma;0&comma;0&comma;0&comma;1&comma;x&comma;1&comma;regular_chain&comma;1&comma;1&comma;1&comma;yx1&comma;1&comma;regular_chain&comma;1&comma;1&comma;0&comma;0&comma;yx1&comma;1&comma;regular_chain&comma;1&comma;1&comma;1&comma;1&comma;1&comma;yx1&comma;1&comma;regular_chain&comma;1&comma;1&comma;2&comma;2

(4)

cadCylindricalAlgebraicDecomposeF&comma;R&comma;output&equals;list

cad:=1&comma;1&comma;regular_chain&comma;1&comma;1&comma;2&comma;2&comma;1&comma;2&comma;regular_chain&comma;1&comma;1&comma;1&comma;1&comma;1&comma;3&comma;regular_chain&comma;1&comma;1&comma;0&comma;0&comma;2&comma;1&comma;regular_chain&comma;0&comma;0&comma;0&comma;0&comma;3&comma;1&comma;regular_chain&comma;1&comma;1&comma;0&comma;0&comma;3&comma;2&comma;regular_chain&comma;1&comma;1&comma;1&comma;1&comma;3&comma;3&comma;regular_chain&comma;1&comma;1&comma;2&comma;2

(5)

For a more complicated example, compute the cylindrical algebraic decomposition of the parametric parabola. The output is a CAD of four-dimensional real space with 27 cells.

RPolynomialRingx&comma;c&comma;b&comma;a

R:=polynomial_ring

(6)

Fax2&plus;bx&plus;c

F:=ax2&plus;bx&plus;c

(7)

The default is the piecewise format. When many cells are present the 'output'='cadcell' and 'output'='rootof' formats are useful.

cadCylindricalAlgebraicDecomposeF&comma;R&comma;output&equals;cadcell

cad:=cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell

(8)

cadCylindricalAlgebraicDecomposeF&comma;R&comma;output&equals;&apos;rootof&apos;

cad:=a<0&comma;b&equals;b&comma;c<14b2a&comma;x&equals;x&comma;a<0&comma;b&equals;b&comma;c&equals;14b2a&comma;x<12ba&comma;a<0&comma;b&equals;b&comma;c&equals;14b2a&comma;x&equals;12ba&comma;a<0&comma;b&equals;b&comma;c&equals;14b2a&comma;12ba<x&comma;a<0&comma;b&equals;b&comma;14b2a<c&comma;x<12b&plus;4ac&plus;b2a&comma;a<0&comma;b&equals;b&comma;14b2a<c&comma;x&equals;12b&plus;4ac&plus;b2a&comma;a<0&comma;b&equals;b&comma;14b2a<c&comma;12b&plus;4ac&plus;b2a<x&comma;x<12b&plus;4ac&plus;b2a&comma;a<0&comma;b&equals;b&comma;14b2a<c&comma;x&equals;12b&plus;4ac&plus;b2a&comma;a<0&comma;b&equals;b&comma;14b2a<c&comma;12b&plus;4ac&plus;b2a<x&comma;a&equals;0&comma;b<0&comma;c&equals;c&comma;x<cb&comma;a&equals;0&comma;b<0&comma;c&equals;c&comma;x&equals;cb&comma;a&equals;0&comma;b<0&comma;c&equals;c&comma;cb<x&comma;a&equals;0&comma;b&equals;0&comma;c<0&comma;x&equals;x&comma;a&equals;0&comma;b&equals;0&comma;c&equals;0&comma;x&equals;x&comma;a&equals;0&comma;b&equals;0&comma;0<c&comma;x&equals;x&comma;a&equals;0&comma;0<b&comma;c&equals;c&comma;x<cb&comma;a&equals;0&comma;0<b&comma;c&equals;c&comma;x&equals;cb&comma;a&equals;0&comma;0<b&comma;c&equals;c&comma;cb<x&comma;0<a&comma;b&equals;b&comma;c<14b2a&comma;x<12b&plus;4ac&plus;b2a&comma;0<a&comma;b&equals;b&comma;c<14b2a&comma;x&equals;12b&plus;4ac&plus;b2a&comma;0<a&comma;b&equals;b&comma;c<14b2a&comma;12b&plus;4ac&plus;b2a<x&comma;x<12b&plus;4ac&plus;b2a&comma;0<a&comma;b&equals;b&comma;c<14b2a&comma;x&equals;12b&plus;4ac&plus;b2a&comma;0<a&comma;b&equals;b&comma;c<14b2a&comma;12b&plus;4ac&plus;b2a<x&comma;0<a&comma;b&equals;b&comma;c&equals;14b2a&comma;x<12ba&comma;0<a&comma;b&equals;b&comma;c&equals;14b2a&comma;x&equals;12ba&comma;0<a&comma;b&equals;b&comma;c&equals;14b2a&comma;12ba<x&comma;0<a&comma;b&equals;b&comma;14b2a<c&comma;x&equals;x

(9)

The usage of input lists of semi-algebraic systems is illustrated below.

RPolynomialRingx&comma;a&comma;b

R:=polynomial_ring

(10)

cadCylindricalAlgebraicDecomposex2a&comma;x&plus;b&comma;R&comma;output&equals;cadcell

cad:=cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell&comma;cad_cell

(11)

cadCylindricalAlgebraicDecomposex2a&equals;0&comma;x&plus;b&equals;0&comma;R&comma;output&equals;cadcell

cad:=cad_cell&comma;cad_cell&comma;cad_cell

(12)

cadCylindricalAlgebraicDecomposex2a&equals;0&comma;x&plus;b&equals;0&comma;R&comma;output&equals;&apos;rootof&apos;

cad:=b<0&comma;a&equals;b2&comma;x&equals;b&comma;b&equals;0&comma;a&equals;0&comma;x&equals;b&comma;0<b&comma;a&equals;b2&comma;x&equals;b

(13)

To understand the effect of a list of two semi-algebraic systems, consider the following very simple example.

cadCylindricalAlgebraicDecomposexa&comma;R&comma;output&equals;&apos;rootof&apos;

cad:=b&equals;b&comma;a&equals;a&comma;x<a&comma;b&equals;b&comma;a&equals;a&comma;x&equals;a&comma;b&equals;b&comma;a&equals;a&comma;a<x

(14)

cadCylindricalAlgebraicDecompose0<xa&comma;R&comma;output&equals;&apos;rootof&apos;

cad:=b&equals;b&comma;a&equals;a&comma;a<x

(15)

cadCylindricalAlgebraicDecomposex&plus;b&comma;R&comma;output&equals;&apos;rootof&apos;

cad:=b&equals;b&comma;a&equals;a&comma;x<b&comma;b&equals;b&comma;a&equals;a&comma;x&equals;b&comma;b&equals;b&comma;a&equals;a&comma;b<x

(16)

cadCylindricalAlgebraicDecomposex&plus;b&equals;0&comma;R&comma;output&equals;&apos;rootof&apos;

cad:=b&equals;b&comma;a&equals;a&comma;x&equals;b

(17)

cadCylindricalAlgebraicDecomposex&plus;b&equals;0&comma;0<xa&comma;R&comma;output&equals;&apos;rootof&apos;

cad:=b&equals;b&comma;a<b&comma;a<x&comma;x<b&comma;b&equals;b&comma;a<b&comma;x&equals;b&comma;b&equals;b&comma;a<b&comma;b<x&comma;b&equals;b&comma;a&equals;b&comma;x&equals;b&comma;b&equals;b&comma;a&equals;b&comma;b<x&comma;b&equals;b&comma;b<a&comma;x&equals;b&comma;b&equals;b&comma;b<a&comma;a<x

(18)

Compatibility

• 

The lsas, 'output'='cadcell' and 'output'='rootof' parameters were introduced in Maple 16.

• 

The output option was introduced in Maple 16.

• 

For more information on Maple 16 changes, see Updates in Maple 16.

See Also

ComprehensiveTriangularize

CylindricalDecompose

Display

PartialCylindricalAlgebraicDecomposition

RealComprehensiveTriangularize

RealRootClassification

RealTriangularize

RegularChains

SamplePoints

SemiAlgebraicSetTools

SeparateZeros

SuggestVariableOrder

Triangularize

 


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam