 RegularChains[SemiAlgebraicSetTools] - Maple Programming Help

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 CylindricalAlgebraicDecompose(F, R, outopt, methopt) CylindricalAlgebraicDecompose(lsas, R, outopt, methopt, optopt)

Parameters

 F - list of polynomials of R R - polynomial ring lsas - list of semi-algebraic systems of R outopt - (optional) keyword option of the form output = value methopt - (optional) keyword option of the form method = value optopt - (optional) keyword option of the form optimization = value

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 option outopt. Its possible values are '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 cylindricity 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.
 The default algorithm of CylindricalAlgebraicDecompose is an incremental algorithm (CM) based on triangular decompositions, and proposed by Changbo Chen and Marc Moreno Maza in ASCM 2012. This default algorithm is also available through the option method=incremental. An alternative algorithm (CMXY) proposed by Changbo Chen, Marc Moreno Maza, Bican Xia and Lu Yang at ISSAC 2009, which is also the first generation of algorithm for computing CAD based on triangular decompositions, is available through the option method=recursive.
 • The CM algorithm can take advantage of equational constraints given in a single semi-algebraic system.  That is, if the input is a list of polynomial constraints involving equations, by default, the option optimization=EC is enabled. To disable such optimization, one sets optimization=false.
 • If the input is a list of polynomial constraints, by default, an algorithm (RC-TTICAD) for computing truth-table invariant CAD is used to compute a smaller CAD. One can use the option optimization=TTICAD or optimization=EC to enable or disable it, respectively.
 • For mathematical definitions of the types squarefree_semi_algebraic_system, semi_algebraic_set and cad_cell, see the SemiAlgebraicSetTools help page.
 • Variable orders play a crucial role in the efficiency of CAD computation. The command SuggestVariableOrder computes such orders heuristically.

Examples

 > $\mathrm{with}\left(\mathrm{RegularChains}\right):$
 > $\mathrm{with}\left(\mathrm{ChainTools}\right):$
 > $\mathrm{with}\left(\mathrm{SemiAlgebraicSetTools}\right):$

Define a ring of polynomials.

 > $R≔\mathrm{PolynomialRing}\left(\left[y,x\right]\right)$
 ${R}{≔}{\mathrm{polynomial_ring}}$ (1)

Define a set of equations.

 > $F≔\left[xy-1\right]$
 ${F}{≔}\left[{x}{}{y}{-}{1}\right]$ (2)

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

 > $\mathrm{cad}≔\mathrm{CylindricalAlgebraicDecompose}\left(F,R\right)$
 ${\mathrm{cad}}{≔}{\mathrm{c_a_d}}$ (3)

The output CAD is described by a nested piecewise function. The outmost piecewise function is a function with three conditions $x<0$, $x=0$, and $0. 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.

 > $\mathrm{cad}≔\mathrm{CylindricalAlgebraicDecompose}\left(F,R,\mathrm{output}=\mathrm{tree}\right)$
 ${\mathrm{cad}}{≔}\left[{1}{,}\left[\left[\left[{-1}{,}{x}{,}{1}\right]{,}\left[{\mathrm{regular_chain}}{,}\left[\left[{-}\frac{{1}}{{2}}{,}{-}\frac{{1}}{{2}}\right]\right]\right]\right]{,}\left[\left[\left[{-1}{,}{y}{}{x}{-}{1}{,}{1}\right]{,}\left[{\mathrm{regular_chain}}{,}\left[\left[{-}\frac{{1}}{{2}}{,}{-}\frac{{1}}{{2}}\right]{,}\left[{-}\frac{{5}}{{2}}{,}{-}\frac{{5}}{{2}}\right]\right]\right]\right]\right]{,}\left[\left[\left[{y}{}{x}{-}{1}{,}{1}\right]{,}\left[{\mathrm{regular_chain}}{,}\left[\left[{-}\frac{{1}}{{2}}{,}{-}\frac{{1}}{{2}}\right]{,}\left[{-2}{,}{-2}\right]\right]\right]\right]\right]{,}\left[\left[\left[{1}{,}{y}{}{x}{-}{1}{,}{1}\right]{,}\left[{\mathrm{regular_chain}}{,}\left[\left[{-}\frac{{1}}{{2}}{,}{-}\frac{{1}}{{2}}\right]{,}\left[{-}\frac{{3}}{{2}}{,}{-}\frac{{3}}{{2}}\right]\right]\right]\right]\right]\right]{,}\left[\left[\left[{x}{,}{1}\right]{,}\left[{\mathrm{regular_chain}}{,}\left[\left[{0}{,}{0}\right]\right]\right]\right]{,}\left[\left[\left[{1}\right]{,}\left[{\mathrm{regular_chain}}{,}\left[\left[{0}{,}{0}\right]{,}\left[{0}{,}{0}\right]\right]\right]\right]\right]\right]{,}\left[\left[\left[{1}{,}{x}{,}{1}\right]{,}\left[{\mathrm{regular_chain}}{,}\left[\left[\frac{{1}}{{2}}{,}\frac{{1}}{{2}}\right]\right]\right]\right]{,}\left[\left[\left[{-1}{,}{y}{}{x}{-}{1}{,}{1}\right]{,}\left[{\mathrm{regular_chain}}{,}\left[\left[\frac{{1}}{{2}}{,}\frac{{1}}{{2}}\right]{,}\left[\frac{{3}}{{2}}{,}\frac{{3}}{{2}}\right]\right]\right]\right]\right]{,}\left[\left[\left[{y}{}{x}{-}{1}{,}{1}\right]{,}\left[{\mathrm{regular_chain}}{,}\left[\left[\frac{{1}}{{2}}{,}\frac{{1}}{{2}}\right]{,}\left[{2}{,}{2}\right]\right]\right]\right]\right]{,}\left[\left[\left[{1}{,}{y}{}{x}{-}{1}{,}{1}\right]{,}\left[{\mathrm{regular_chain}}{,}\left[\left[\frac{{1}}{{2}}{,}\frac{{1}}{{2}}\right]{,}\left[\frac{{5}}{{2}}{,}\frac{{5}}{{2}}\right]\right]\right]\right]\right]\right]\right]$ (4)
 > $\mathrm{cad}≔\mathrm{CylindricalAlgebraicDecompose}\left(F,R,\mathrm{output}=\mathrm{list}\right)$
 ${\mathrm{cad}}{≔}\left[\left[\left[{1}{,}{1}\right]{,}\left[{\mathrm{regular_chain}}{,}\left[\left[{-}\frac{{1}}{{2}}{,}{-}\frac{{1}}{{2}}\right]{,}\left[{-}\frac{{5}}{{2}}{,}{-}\frac{{5}}{{2}}\right]\right]\right]\right]{,}\left[\left[{1}{,}{2}\right]{,}\left[{\mathrm{regular_chain}}{,}\left[\left[{-}\frac{{1}}{{2}}{,}{-}\frac{{1}}{{2}}\right]{,}\left[{-2}{,}{-2}\right]\right]\right]\right]{,}\left[\left[{1}{,}{3}\right]{,}\left[{\mathrm{regular_chain}}{,}\left[\left[{-}\frac{{1}}{{2}}{,}{-}\frac{{1}}{{2}}\right]{,}\left[{-}\frac{{3}}{{2}}{,}{-}\frac{{3}}{{2}}\right]\right]\right]\right]{,}\left[\left[{2}{,}{1}\right]{,}\left[{\mathrm{regular_chain}}{,}\left[\left[{0}{,}{0}\right]{,}\left[{0}{,}{0}\right]\right]\right]\right]{,}\left[\left[{3}{,}{1}\right]{,}\left[{\mathrm{regular_chain}}{,}\left[\left[\frac{{1}}{{2}}{,}\frac{{1}}{{2}}\right]{,}\left[\frac{{3}}{{2}}{,}\frac{{3}}{{2}}\right]\right]\right]\right]{,}\left[\left[{3}{,}{2}\right]{,}\left[{\mathrm{regular_chain}}{,}\left[\left[\frac{{1}}{{2}}{,}\frac{{1}}{{2}}\right]{,}\left[{2}{,}{2}\right]\right]\right]\right]{,}\left[\left[{3}{,}{3}\right]{,}\left[{\mathrm{regular_chain}}{,}\left[\left[\frac{{1}}{{2}}{,}\frac{{1}}{{2}}\right]{,}\left[\frac{{5}}{{2}}{,}\frac{{5}}{{2}}\right]\right]\right]\right]\right]$ (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.

 > $R≔\mathrm{PolynomialRing}\left(\left[x,c,b,a\right]\right)$
 ${R}{≔}{\mathrm{polynomial_ring}}$ (6)
 > $F≔\left[a{x}^{2}+bx+c\right]$
 ${F}{≔}\left[{a}{}{{x}}^{{2}}{+}{b}{}{x}{+}{c}\right]$ (7)

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

 > $\mathrm{cad}≔\mathrm{CylindricalAlgebraicDecompose}\left(F,R,\mathrm{output}=\mathrm{cadcell}\right)$
 ${\mathrm{cad}}{≔}\left[{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}\right]$ (8)
 > $\mathrm{cad}≔\mathrm{CylindricalAlgebraicDecompose}\left(F,R,\mathrm{output}='\mathrm{rootof}'\right)$
 ${\mathrm{cad}}{≔}\left[\left[{a}{<}{0}{,}{b}{=}{b}{,}{c}{<}\frac{{{b}}^{{2}}}{{4}{}{a}}{,}{x}{=}{x}\right]{,}\left[{a}{<}{0}{,}{b}{=}{b}{,}{c}{=}\frac{{{b}}^{{2}}}{{4}{}{a}}{,}{x}{<}{-}\frac{{b}}{{2}{}{a}}\right]{,}\left[{a}{<}{0}{,}{b}{=}{b}{,}{c}{=}\frac{{{b}}^{{2}}}{{4}{}{a}}{,}{x}{=}{-}\frac{{b}}{{2}{}{a}}\right]{,}\left[{a}{<}{0}{,}{b}{=}{b}{,}{c}{=}\frac{{{b}}^{{2}}}{{4}{}{a}}{,}{-}\frac{{b}}{{2}{}{a}}{<}{x}\right]{,}\left[{a}{<}{0}{,}{b}{=}{b}{,}\frac{{{b}}^{{2}}}{{4}{}{a}}{<}{c}{,}{x}{<}\frac{{-}{b}{+}\sqrt{{-}{4}{}{c}{}{a}{+}{{b}}^{{2}}}}{{2}{}{a}}\right]{,}\left[{a}{<}{0}{,}{b}{=}{b}{,}\frac{{{b}}^{{2}}}{{4}{}{a}}{<}{c}{,}{x}{=}\frac{{-}{b}{+}\sqrt{{-}{4}{}{c}{}{a}{+}{{b}}^{{2}}}}{{2}{}{a}}\right]{,}\left[{a}{<}{0}{,}{b}{=}{b}{,}\frac{{{b}}^{{2}}}{{4}{}{a}}{<}{c}{,}\frac{{-}{b}{+}\sqrt{{-}{4}{}{c}{}{a}{+}{{b}}^{{2}}}}{{2}{}{a}}{<}{x}{\wedge }{x}{<}{-}\frac{{b}{+}\sqrt{{-}{4}{}{c}{}{a}{+}{{b}}^{{2}}}}{{2}{}{a}}\right]{,}\left[{a}{<}{0}{,}{b}{=}{b}{,}\frac{{{b}}^{{2}}}{{4}{}{a}}{<}{c}{,}{x}{=}{-}\frac{{b}{+}\sqrt{{-}{4}{}{c}{}{a}{+}{{b}}^{{2}}}}{{2}{}{a}}\right]{,}\left[{a}{<}{0}{,}{b}{=}{b}{,}\frac{{{b}}^{{2}}}{{4}{}{a}}{<}{c}{,}{-}\frac{{b}{+}\sqrt{{-}{4}{}{c}{}{a}{+}{{b}}^{{2}}}}{{2}{}{a}}{<}{x}\right]{,}\left[{a}{=}{0}{,}{b}{<}{0}{,}{c}{=}{c}{,}{x}{<}{-}\frac{{c}}{{b}}\right]{,}\left[{a}{=}{0}{,}{b}{<}{0}{,}{c}{=}{c}{,}{x}{=}{-}\frac{{c}}{{b}}\right]{,}\left[{a}{=}{0}{,}{b}{<}{0}{,}{c}{=}{c}{,}{-}\frac{{c}}{{b}}{<}{x}\right]{,}\left[{a}{=}{0}{,}{b}{=}{0}{,}{c}{<}{0}{,}{x}{=}{x}\right]{,}\left[{a}{=}{0}{,}{b}{=}{0}{,}{c}{=}{0}{,}{x}{=}{x}\right]{,}\left[{a}{=}{0}{,}{b}{=}{0}{,}{0}{<}{c}{,}{x}{=}{x}\right]{,}\left[{a}{=}{0}{,}{0}{<}{b}{,}{c}{=}{c}{,}{x}{<}{-}\frac{{c}}{{b}}\right]{,}\left[{a}{=}{0}{,}{0}{<}{b}{,}{c}{=}{c}{,}{x}{=}{-}\frac{{c}}{{b}}\right]{,}\left[{a}{=}{0}{,}{0}{<}{b}{,}{c}{=}{c}{,}{-}\frac{{c}}{{b}}{<}{x}\right]{,}\left[{0}{<}{a}{,}{b}{=}{b}{,}{c}{<}\frac{{{b}}^{{2}}}{{4}{}{a}}{,}{x}{<}{-}\frac{{b}{+}\sqrt{{-}{4}{}{c}{}{a}{+}{{b}}^{{2}}}}{{2}{}{a}}\right]{,}\left[{0}{<}{a}{,}{b}{=}{b}{,}{c}{<}\frac{{{b}}^{{2}}}{{4}{}{a}}{,}{x}{=}{-}\frac{{b}{+}\sqrt{{-}{4}{}{c}{}{a}{+}{{b}}^{{2}}}}{{2}{}{a}}\right]{,}\left[{0}{<}{a}{,}{b}{=}{b}{,}{c}{<}\frac{{{b}}^{{2}}}{{4}{}{a}}{,}{-}\frac{{b}{+}\sqrt{{-}{4}{}{c}{}{a}{+}{{b}}^{{2}}}}{{2}{}{a}}{<}{x}{\wedge }{x}{<}\frac{{-}{b}{+}\sqrt{{-}{4}{}{c}{}{a}{+}{{b}}^{{2}}}}{{2}{}{a}}\right]{,}\left[{0}{<}{a}{,}{b}{=}{b}{,}{c}{<}\frac{{{b}}^{{2}}}{{4}{}{a}}{,}{x}{=}\frac{{-}{b}{+}\sqrt{{-}{4}{}{c}{}{a}{+}{{b}}^{{2}}}}{{2}{}{a}}\right]{,}\left[{0}{<}{a}{,}{b}{=}{b}{,}{c}{<}\frac{{{b}}^{{2}}}{{4}{}{a}}{,}\frac{{-}{b}{+}\sqrt{{-}{4}{}{c}{}{a}{+}{{b}}^{{2}}}}{{2}{}{a}}{<}{x}\right]{,}\left[{0}{<}{a}{,}{b}{=}{b}{,}{c}{=}\frac{{{b}}^{{2}}}{{4}{}{a}}{,}{x}{<}{-}\frac{{b}}{{2}{}{a}}\right]{,}\left[{0}{<}{a}{,}{b}{=}{b}{,}{c}{=}\frac{{{b}}^{{2}}}{{4}{}{a}}{,}{x}{=}{-}\frac{{b}}{{2}{}{a}}\right]{,}\left[{0}{<}{a}{,}{b}{=}{b}{,}{c}{=}\frac{{{b}}^{{2}}}{{4}{}{a}}{,}{-}\frac{{b}}{{2}{}{a}}{<}{x}\right]{,}\left[{0}{<}{a}{,}{b}{=}{b}{,}\frac{{{b}}^{{2}}}{{4}{}{a}}{<}{c}{,}{x}{=}{x}\right]\right]$ (9)

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

 > $R≔\mathrm{PolynomialRing}\left(\left[x,a,b\right]\right)$
 ${R}{≔}{\mathrm{polynomial_ring}}$ (10)
 > $\mathrm{cad}≔\mathrm{CylindricalAlgebraicDecompose}\left(\left[{x}^{2}-a,x+b\right],R,\mathrm{output}=\mathrm{cadcell}\right)$
 ${\mathrm{cad}}{≔}\left[{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}{,}{\mathrm{cad_cell}}\right]$ (11)
 > $\mathrm{cad}≔\mathrm{CylindricalAlgebraicDecompose}\left(\left[\left[{x}^{2}-a=0,x+b=0\right]\right],R,\mathrm{output}=\mathrm{cadcell}\right)$
 ${\mathrm{cad}}{≔}\left[{\mathrm{cad_cell}}\right]$ (12)
 > $\mathrm{cad}≔\mathrm{CylindricalAlgebraicDecompose}\left(\left[\left[{x}^{2}-a=0,x+b=0\right]\right],R,\mathrm{output}='\mathrm{rootof}'\right)$
 ${\mathrm{cad}}{≔}\left[\left[{b}{=}{b}{,}{a}{=}{{b}}^{{2}}{,}{x}{=}{-}{b}\right]\right]$ (13)

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

 > $\mathrm{cad}≔\mathrm{CylindricalAlgebraicDecompose}\left(\left[x-a\right],R,\mathrm{output}='\mathrm{rootof}'\right)$
 ${\mathrm{cad}}{≔}\left[\left[{b}{=}{b}{,}{a}{=}{a}{,}{x}{<}{a}\right]{,}\left[{b}{=}{b}{,}{a}{=}{a}{,}{x}{=}{a}\right]{,}\left[{b}{=}{b}{,}{a}{=}{a}{,}{a}{<}{x}\right]\right]$ (14)
 > $\mathrm{cad}≔\mathrm{CylindricalAlgebraicDecompose}\left(\left[\left[0
 ${\mathrm{cad}}{≔}\left[\left[{b}{=}{b}{,}{a}{=}{a}{,}{a}{<}{x}\right]\right]$ (15)
 > $\mathrm{cad}≔\mathrm{CylindricalAlgebraicDecompose}\left(\left[x+b\right],R,\mathrm{output}='\mathrm{rootof}'\right)$
 ${\mathrm{cad}}{≔}\left[\left[{b}{=}{b}{,}{a}{=}{a}{,}{x}{<}{-}{b}\right]{,}\left[{b}{=}{b}{,}{a}{=}{a}{,}{x}{=}{-}{b}\right]{,}\left[{b}{=}{b}{,}{a}{=}{a}{,}{-}{b}{<}{x}\right]\right]$ (16)
 > $\mathrm{cad}≔\mathrm{CylindricalAlgebraicDecompose}\left(\left[\left[x+b=0\right]\right],R,\mathrm{output}='\mathrm{rootof}'\right)$
 ${\mathrm{cad}}{≔}\left[\left[{b}{=}{b}{,}{a}{=}{a}{,}{x}{=}{-}{b}\right]\right]$ (17)
 > $\mathrm{cad}≔\mathrm{CylindricalAlgebraicDecompose}\left(\left[\left[x+b=0\right],\left[0
 ${\mathrm{cad}}{≔}\left[\left[{b}{=}{b}{,}{a}{<}{-}{b}{,}{a}{<}{x}\right]{,}\left[{b}{=}{b}{,}{a}{=}{-}{b}{,}{-}{b}{\le }{x}\right]{,}\left[{b}{=}{b}{,}{-}{b}{<}{a}{,}{x}{=}{-}{b}\right]{,}\left[{b}{=}{b}{,}{-}{b}{<}{a}{,}{a}{<}{x}\right]\right]$ (18)

The usage of the different methods and optimizations is illustrated below.

 > $R≔\mathrm{PolynomialRing}\left(\left[y,x\right]\right)$
 ${R}{≔}{\mathrm{polynomial_ring}}$ (19)
 > $F≔\left[{y}^{2}-x\right]$
 ${F}{≔}\left[{{y}}^{{2}}{-}{x}\right]$ (20)
 > $\mathrm{cad}≔\mathrm{CylindricalAlgebraicDecompose}\left(F,R,\mathrm{method}=\mathrm{recursive},\mathrm{output}=\mathrm{piecewise}\right)$
 ${\mathrm{cad}}{≔}\left\{\begin{array}{cc}{1}& {x}{<}{0}\\ \left\{\begin{array}{cc}{1}& {y}{<}{0}\\ {1}& {y}{=}{0}\\ {1}& {0}{<}{y}\end{array}\right\& {x}{=}{0}\\ \left\{\begin{array}{cc}{1}& {y}{<}{-}\sqrt{{x}}\\ {1}& {y}{=}{-}\sqrt{{x}}\\ {1}& {-}\sqrt{{x}}{<}{y}{\wedge }{y}{<}\sqrt{{x}}\\ {1}& {y}{=}\sqrt{{x}}\\ {1}& \sqrt{{x}}{<}{y}\end{array}\right\& {0}{<}{x}\end{array}\right\$ (21)
 > $R≔\mathrm{PolynomialRing}\left(\left[y,x\right]\right)$
 ${R}{≔}{\mathrm{polynomial_ring}}$ (22)
 > $F≔\left[{x}^{2}+{y}^{2}-1=0,{y}^{2}-x=0\right]$
 ${F}{≔}\left[{{x}}^{{2}}{+}{{y}}^{{2}}{-}{1}{=}{0}{,}{{y}}^{{2}}{-}{x}{=}{0}\right]$ (23)
 > $\mathrm{cad}≔\mathrm{CylindricalAlgebraicDecompose}\left(F,R,\mathrm{optimization}='\mathrm{EC}',\mathrm{output}=\mathrm{allcell}\right):$
 > $\mathrm{nops}\left(\mathrm{cad}\right)$
 ${9}$ (24)
 > $\mathrm{cad2}≔\mathrm{CylindricalAlgebraicDecompose}\left(F,R,\mathrm{optimization}='\mathrm{false}',\mathrm{output}=\mathrm{allcell}\right):$
 > $\mathrm{nops}\left(\mathrm{cad2}\right)$
 ${53}$ (25)

Compatibility

 • The lsas parameter was introduced in Maple 16.
 • The output option was introduced in Maple 16.