compute a comprehensive triangular decomposition of a parametric polynomial system - Maple Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Factorization and Solving Equations : RegularChains : ParametricSystemTools Subpackage : RegularChains/ParametricSystemTools/ComprehensiveTriangularize

RegularChains[ParametricSystemTools][ComprehensiveTriangularize] - compute a comprehensive triangular decomposition of a parametric polynomial system

RegularChains[ParametricSystemTools][RealComprehensiveTriangularize] - compute a comprehensive triangular decomposition over the reals of a parametric polynomial system

Calling Sequence

ComprehensiveTriangularize(F, d, R)

ComprehensiveTriangularize(F, H, d, R)

ComprehensiveTriangularize(CS, d, R)

ComprehensiveTriangularize(F, d, R, 'disjoint'='yes')

ComprehensiveTriangularize(F, H, d, R, 'disjoint'='yes')

ComprehensiveTriangularize(CS, d, R, 'disjoint'='yes')

ComprehensiveTriangularize(F, d, R, 'output'='piecewise')

ComprehensiveTriangularize(F, H, d, R, 'output'='piecewise')

ComprehensiveTriangularize(CS, d, R, 'output'='piecewise')

RealComprehensiveTriangularize(sys, d, R)

RealComprehensiveTriangularize(sys, d, R, 'output'='semialgebraicset')

RealComprehensiveTriangularize(sys, d, R, 'output'='cadcell')

RealComprehensiveTriangularize(F, N, P, H, d, R)

RealComprehensiveTriangularize(F, N, P, H, d, R, 'output'='semialgebraicset')

RealComprehensiveTriangularize(F, N, P, H, d, R, 'output'='cadcell')

RealComprehensiveTriangularize(rctd, R, n)

RealComprehensiveTriangularize(rctd, R, n..'infinity')

RealComprehensiveTriangularize(rctd, R, 'infinity')

RealComprehensiveTriangularize(rctd, R, n..'finite')

RealComprehensiveTriangularize(rctd, R, 'finite')

RealComprehensiveTriangularize(sys, R, n)

RealComprehensiveTriangularize(sys, R, n..'infinity')

RealComprehensiveTriangularize(sys, R, 'infinity')

RealComprehensiveTriangularize(sys, R, n..'finite')

RealComprehensiveTriangularize(sys, R, 'finite')

Parameters

F

-

list of polynomials

d

-

number of parameters

R

-

polynomial ring

H

-

list of polynomials

CS

-

constructible set

sys

-

semi-algebraic system

N

-

list of polynomials

P

-

list of polynomials

rctd

-

data-structure returned by RealComprehensiveTriangularize

n

-

prescribed number of solutions

n..'infinity'

-

at least n solutions

'infinity'

-

infinitely many solutions

n..'finite'

-

finitely many and at least n solutions

'finite'

-

finitely many solutions

'disjoint'='yes'

-

(optional) boolean flag

'output'='piecewise'

-

(optional) boolean flag

'output'=semialgebraicset'

-

(optional) boolean flag

'output'='cadcell'

-

(optional) boolean flag

Description

• 

The command ComprehensiveTriangularize(CS, d, R) returns a comprehensive triangular decomposition (CTD) of the constructible set CS, with respect to the last d variables of R.

• 

The command ComprehensiveTriangularize(F, H, d, R) returns a comprehensive triangular decomposition (CTD) of the constructible set V(F)-V(H), with respect to the last d variables of R.

• 

The command ComprehensiveTriangularize(F, d, R) returns a comprehensive triangular decomposition (CTD) of the variety V(F), with respect to the last d variables of R.

• 

The output of ComprehensiveTriangularize(CS, d, R) consists of two parts. The first part is a pre-comprehensive triangular decomposition S of CS with respect to the last d variables of R.

  

The second part is a list L of pairs; the first item of each pair is a constructible set and the second item is a list of indices (positive integers) such that the union of these constructible sets forms a partition of the projection of CS onto the parameter space. Moreover, for each part (or cell) C, the list of positive integers associated with it gives the positions of the regular chains in S satisfying the following property: for each parameter value u in C, those regular chains specialized at u form a triangular decomposition of CS specialized at u.

• 

If 'disjoint'='yes' is present, the computed CTD satisfies two additional properties. First, each regular system in S is square-free. Secondly, for each part (or cell) C, the regular chains associated with C separate disjointly at any parameter value u of C, that is, those regular chains specialize at u into square-free regular chains whose quasi-components are pairwise disjoint.

• 

If 'output'='piecewise' is present, the output is organized as a tree. More precisely the cells in the parameter space are organized in a natural manner as a tree.

• 

The command RealComprehensiveTriangularize(sys, d, R) returns a real comprehensive triangular decomposition (RCTD) of the semi-algebraic system sys, with respect to the last d variables of R.  These last d are regarded as the parameters of sys. The constraints in sys can be any polynomial equations, inequations or inequalities given by polynomials of R. The zero set of sys is the set of the real solutions of the polynomial system defined by sys.

• 

The command RealComprehensiveTriangularize(F, N, P, H, d, R) returns a RCTD of the semi-algebraic system defined by F, N, P, H and with respect to the last d variables of R.  See SemiAlgebraicSetTools or RealTriangularize for the specification of the semi-algebraic system defined by four polynomial lists F, N, P, H.

• 

All uses of RealComprehensiveTriangularize assume that R has characteristic zero and no parameters, such that the base field of R is the field of rational numbers.

• 

The output of RealComprehensiveTriangularize(sys, d, R) or RealComprehensiveTriangularize(F, N, P, H, d, R) is a list of two items.

• 

The first one is a list systems of squarefree triangular semi-algebraic systems and the second one is a list cells of semi-algebraic sets forming a partition of the parameter space. Above each of these semi-algebraic sets, the solutions of the input semi-algebraic system is described by a subset of systems, using the same indexing convention as for ComprehensiveTriangularize.

• 

Each of these semi-algebraic sets is a disjoint union of CAD cells; these cells are connected such that the solutions above a cell depend continuously on the parameters of that cell. Moreover, if the input system admits finitely many solutions above that cell, then the graphs of the functions (from the corresponding items in systems) describing those solutions are disjoint.

• 

These properties make it possible to count the number of real solutions of the input system depending on the parameters. For this reason the output rctd of RealComprehensiveTriangularize(sys, d, R) or RealComprehensiveTriangularize(F, N, P, H, d, R) can be used as first input argument of RealComprehensiveTriangularize together with a prescribed number or number range of solution. In this case only the items of systems and cells corresponding to the prescribed number or number range are returned. See the examples below.

• 

output=cadcell and output=semialgebraicset options controls the representation of the output format.  The default is semialgebraicset.

• 

For a mathematical definition of the type regular_chain, see the page RegularChains.

• 

For mathematical definitions of the types regular_system and constructible_set, see the page ConstructibleSetTools.

• 

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

Examples

withRegularChains:withConstructibleSetTools:withParametricSystemTools:

R:=PolynomialRingx,y,s

R:=polynomial_ring

(1)

F:=sy+1x,sx+1y

F:=sy+1x,sx+1y

(2)

A comprehensive triangular decomposition of F with respect to parameter s is as follows.

pctd,cells:=ComprehensiveTriangularizeF,1,R

pctd,cells:=regular_chain,regular_chain,regular_chain,constructible_set,3,2,constructible_set,1

(3)

The first part of the output is the pre-comprehensive triangular decomposition of F which consists of three regular chains.

pctd

regular_chain,regular_chain,regular_chain

(4)

mapInfo,pctd,R

y+1xs,y2+ys,x+1,y+1,s,x,y,s

(5)

The projection of V(F) onto the parameter space has been partitioned into two disjoint constructible sets.

cs1:=cells11;Infocs1,R

cs1:=constructible_set

s,1

(6)

cs2:=cells21;Infocs2,R

cs2:=constructible_set

,s

(7)

Thus, when the parameter value s is in cs1, the last two regular chains (after specialization) form a triangular decomposition of F(s). Otherwise, s is in cs2, then the first regular chain forms a triangular decomposition of F(s).

Computing a CTD of a constructible set:

F:=sy+1x,sx+1y

F:=sy+1x,sx+1y

(8)

H:=x+y1

H:=x+y1

(9)

cs:=GeneralConstructF,H,R

cs:=constructible_set

(10)

ComprehensiveTriangularizecs,1,R

regular_system,regular_system,regular_system,regular_system,constructible_set,1,constructible_set,2,4,constructible_set,3

(11)

When the option 'disjoint'='yes' is present, the format of the output is changed a little bit: the partition of the parameter space is given by the union of the constructible sets (the right items in the pairs) whereas the pre-comprehensive triangular decomposition is given by the union of the regular systems (the left items in the pairs). In each pair, the regular system is a component of the input system above the associated constructible set.

ComprehensiveTriangularizecs,1,R,disjoint=yes

regular_system,regular_system,regular_system,regular_system,regular_system,constructible_set,1,constructible_set,2,4,constructible_set,5,constructible_set,3

(12)

Illustrate the piecewise formatting of the output

ComprehensiveTriangularizeF,H,1,R,output=piecewise

{y2+ys=0,xys+x=0,y+10,y+2s10Ands0,4s30s=0,x+1=0,y+1=0,s=0,x=0,y=0s=04s3=0,2x+3=0,2y+3=04s3=0

(13)

ComprehensiveTriangularizeF,H,1,R,disjoint=yes,output=piecewise

{y2+ys=0,xys+x=0,y+10,y+2s10Ands0,4s+10,4s30s=0,x+1=0,y+1=0,s=0,x=0,y=0s=04s+1=0,2x+1=0,2y+1=04s+1=04s3=0,2x+3=0,2y+3=04s3=0

(14)

The following examples illustrate the use of RealComprehensiveTriangularize.

Define a polynomial ring and a parametric polynomial.

R:=PolynomialRingx,c,b,a

R:=polynomial_ring

(15)

f:=ax2+bx+c

f:=ax2+bx+c

(16)

Solve for the real solutions of f with a>0 regarding a, b, c as parameters.

rctd:=RealComprehensiveTriangularizef&equals;0&comma;0<a&comma;3&comma;R

rctd:=1&comma;squarefree_semi_algebraic_system&comma;2&comma;squarefree_semi_algebraic_system&comma;semi_algebraic_set&comma;&comma;semi_algebraic_set&comma;1&comma;semi_algebraic_set&comma;2

(17)

Display the systems defining the possible solutions

Displayrctd1&comma;R

1&comma;ax2+bx+c=0&comma;2&comma;2ax+b=0

(18)

Display the cells partitioning the parameter space

Displayrctd2&comma;R

&lcub;c<14b2ab&equals;ba<0&comma;&lcub;c&equals;14b2ab&equals;ba<0&comma;&lcub;14b2a<cb&equals;ba<0&comma;&lcub;c&equals;cb&equals;ba&equals;0&comma;&lcub;14b2a<cb&equals;b0<a&comma;&comma;&lcub;c<14b2ab&equals;b0<a&comma;1&comma;&lcub;c&equals;14b2ab&equals;b0<a&comma;2

(19)

Ask for the cases with 2 distinct real solutions.

rctd:=RealComprehensiveTriangularizerctd&comma;R&comma;2

rctd:=1&comma;squarefree_semi_algebraic_system&comma;semi_algebraic_set&comma;1

(20)

Display the solutions and the parameter cells.

Displayrctd&comma;R

1&comma;ax2+bx+c=0&comma;&lcub;c<14b2ab&equals;b0<a&comma;1

(21)

Ask for the cases where f=0 has infinitely many solutions.

rctd:=RealComprehensiveTriangularizef&equals;0&comma;3&comma;R&comma;&infin;

rctd:=1&comma;squarefree_semi_algebraic_system&comma;semi_algebraic_set&comma;1

(22)

Display the solutions and the parameter cells.

Displayrctd&comma;R

1&comma;true&comma;&lcub;c&equals;0b&equals;0a&equals;0&comma;1

(23)

Ask for the cases where f=0 has 2 distinct real solutions.

rctd:=RealComprehensiveTriangularizef&equals;0&comma;3&comma;R&comma;2

rctd:=1&comma;squarefree_semi_algebraic_system&comma;semi_algebraic_set&comma;1

(24)

Display the solutions and the parameter cells.

Displayrctd&comma;R

1&comma;ax2+bx+c=0&comma;&lcub;14b2a<cb&equals;ba<0&comma;&lcub;c<14b2ab&equals;b0<a&comma;1

(25)

Use the cadcell output format.

rctd:=RealComprehensiveTriangularizef&equals;0&comma;3&comma;R&comma;2&comma;output&equals;&apos;cadcell&apos;

rctd:=1&comma;squarefree_semi_algebraic_system&comma;cad_cell&comma;1&comma;cad_cell&comma;1

(26)

Consider another example.

R:=PolynomialRingx&comma;c&comma;b&comma;a&semi;f:=ax3&plus;bx&plus;c

R:=polynomial_ring

f:=ax3&plus;bx&plus;c

(27)

rctd:=RealComprehensiveTriangularizef&equals;0&comma;0<a&comma;3&comma;R

rctd:=1&comma;squarefree_semi_algebraic_system&comma;2&comma;squarefree_semi_algebraic_system&comma;3&comma;squarefree_semi_algebraic_system&comma;semi_algebraic_set&comma;&comma;semi_algebraic_set&comma;1&comma;semi_algebraic_set&comma;2&comma;semi_algebraic_set&comma;3

(28)

Displayrctd1&comma;R

1&comma;ax3+bx+c=0&comma;2&comma;4b2ax26cbax+9c2a+4b3=0&comma;3&comma;x=0

(29)

Displayrctd2&comma;R

&lcub;c&equals;cb<0a<0&comma;&lcub;c<0b&equals;0a<0&comma;&lcub;c&equals;0b&equals;0a<0&comma;&lcub;0<cb&equals;0a<0&comma;&lcub;c<293ab3a0<ba<0&comma;&lcub;c&equals;293ab3a0<ba<0&comma;&lcub;And293ab3a<c&comma;c<293ab3a0<ba<0&comma;&lcub;c&equals;293ab3a0<ba<0&comma;&lcub;293ab3a<c0<ba<0&comma;&lcub;c&equals;cb&equals;ba&equals;0&comma;&comma;&lcub;c<293ab3ab<00<a&comma;&lcub;And293ab3a<c&comma;c<293ab3ab<00<a&comma;&lcub;293ab3a<cb<00<a&comma;&lcub;c<0b&equals;00<a&comma;&lcub;0<cb&equals;00<a&comma;&lcub;c&equals;c0<b0<a&comma;1&comma;&lcub;c&equals;293ab3ab<00<a&comma;&lcub;c&equals;293ab3ab<00<a&comma;2&comma;&lcub;c&equals;0b&equals;00<a&comma;3

(30)

See Also

ConstructibleSet, CylindricalAlgebraicDecompose, CylindricalDecompose, DefiningSet, DiscriminantSet, Info, ParametricSystemTools, PreComprehensiveTriangularize, Projection, RealTriangularize, RegularChains, SemiAlgebraicSetTools, SeparateZeros, Triangularize

References

  

Chen, C.; Golubitsky, O.; Lemaire, F.; Moreno Maza, M.; and Pan, W. "Comprehensive Triangular Decomposition." Proc. CASC 2007, LNCS Vol. 4770: 73-101. Springer, 2007.

  

Chen, C.; and Moreno Maza, M. "Semi-algebraic description of the equilibria of dynamical systems." Proc. Cof the 2011 International Workshop on Computer Algebra in Scientific Computing  (CASC 2011),  LNCS Vol. 6885: 101-125. Springer, 2011.


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