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.

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

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

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

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

$R≔\mathrm{polynomial\_ring}$

$F≔\left[xy-1\right]$

$F≔\left[xy-1\right]$

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

$\mathrm{cad}≔\mathrm{c\_a\_d}$

$\mathrm{cad}≔\mathrm{CylindricalAlgebraicDecompose}\left(F\,R\,\mathrm{output}=\mathrm{tree}\right)$

$\mathrm{cad}≔\left[1\,\left[\left[\left[\mathrm{-1}\,x\,1\right]\,\left[\mathrm{regular\_chain}\,\left[\left[-\frac{1}{2}\,-\frac{1}{2}\right]\right]\right]\right]\,\left[\left[\left[\mathrm{-1}\,yx-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[yx-1\,1\right]\,\left[\mathrm{regular\_chain}\,\left[\left[-\frac{1}{2}\,-\frac{1}{2}\right]\,\left[\mathrm{-2}\,\mathrm{-2}\right]\right]\right]\right]\right]\,\left[\left[\left[1\,yx-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[\mathrm{-1}\,yx-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[yx-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\,yx-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]$

$\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[\mathrm{-2}\,\mathrm{-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]$

$R≔\mathrm{PolynomialRing}\left(\left[x\,c\,b\,a\right]\right)$

$R≔\mathrm{polynomial\_ring}$

$F≔\left[a{x}^2+bx+c\right]$

$F≔\left[a{x}^2+bx+c\right]$

$\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]$

$\mathrm{cad}≔\mathrm{CylindricalAlgebraicDecompose}\left(F\,R\,\mathrm{output}='\mathrm{rootof}'\right)$

$\mathrm{cad}≔\left[\left[a<0\&comma;b=b\&comma;c<\frac{b^2}{4a}\&comma;x=x\right]\&comma;\left[a<0\&comma;b=b\&comma;c=\frac{b^2}{4a}\&comma;x<-\frac{b}{2a}\right]\&comma;\left[a<0\&comma;b=b\&comma;c=\frac{b^2}{4a}\&comma;x=-\frac{b}{2a}\right]\&comma;\left[a<0\&comma;b=b\&comma;c=\frac{b^2}{4a}\&comma;-\frac{b}{2a}<x\right]\&comma;\left[a<0\&comma;b=b\&comma;\frac{b^2}{4a}<c\&comma;x<\frac{-b+\sqrt{-4ca+b^2}}{2a}\right]\&comma;\left[a<0\&comma;b=b\&comma;\frac{b^2}{4a}<c\&comma;x=\frac{-b+\sqrt{-4ca+b^2}}{2a}\right]\&comma;\left[a<0\&comma;b=b\&comma;\frac{b^2}{4a}<c\&comma;\frac{-b+\sqrt{-4ca+b^2}}{2a}<x\wedge x<-\frac{b+\sqrt{-4ca+b^2}}{2a}\right]\&comma;\left[a<0\&comma;b=b\&comma;\frac{b^2}{4a}<c\&comma;x=-\frac{b+\sqrt{-4ca+b^2}}{2a}\right]\&comma;\left[a<0\&comma;b=b\&comma;\frac{b^2}{4a}<c\&comma;-\frac{b+\sqrt{-4ca+b^2}}{2a}<x\right]\&comma;\left[a=0\&comma;b<0\&comma;c=c\&comma;x<-\frac{c}{b}\right]\&comma;\left[a=0\&comma;b<0\&comma;c=c\&comma;x=-\frac{c}{b}\right]\&comma;\left[a=0\&comma;b<0\&comma;c=c\&comma;-\frac{c}{b}<x\right]\&comma;\left[a=0\&comma;b=0\&comma;c<0\&comma;x=x\right]\&comma;\left[a=0\&comma;b=0\&comma;c=0\&comma;x=x\right]\&comma;\left[a=0\&comma;b=0\&comma;0<c\&comma;x=x\right]\&comma;\left[a=0\&comma;0<b\&comma;c=c\&comma;x<-\frac{c}{b}\right]\&comma;\left[a=0\&comma;0<b\&comma;c=c\&comma;x=-\frac{c}{b}\right]\&comma;\left[a=0\&comma;0<b\&comma;c=c\&comma;-\frac{c}{b}<x\right]\&comma;\left[0<a\&comma;b=b\&comma;c<\frac{b^2}{4a}\&comma;x<-\frac{b+\sqrt{-4ca+b^2}}{2a}\right]\&comma;\left[0<a\&comma;b=b\&comma;c<\frac{b^2}{4a}\&comma;x=-\frac{b+\sqrt{-4ca+b^2}}{2a}\right]\&comma;\left[0<a\&comma;b=b\&comma;c<\frac{b^2}{4a}\&comma;-\frac{b+\sqrt{-4ca+b^2}}{2a}<x\wedge x<\frac{-b+\sqrt{-4ca+b^2}}{2a}\right]\&comma;\left[0<a\&comma;b=b\&comma;c<\frac{b^2}{4a}\&comma;x=\frac{-b+\sqrt{-4ca+b^2}}{2a}\right]\&comma;\left[0<a\&comma;b=b\&comma;c<\frac{b^2}{4a}\&comma;\frac{-b+\sqrt{-4ca+b^2}}{2a}<x\right]\&comma;\left[0<a\&comma;b=b\&comma;c=\frac{b^2}{4a}\&comma;x<-\frac{b}{2a}\right]\&comma;\left[0<a\&comma;b=b\&comma;c=\frac{b^2}{4a}\&comma;x=-\frac{b}{2a}\right]\&comma;\left[0<a\&comma;b=b\&comma;c=\frac{b^2}{4a}\&comma;-\frac{b}{2a}<x\right]\&comma;\left[0<a\&comma;b=b\&comma;\frac{b^2}{4a}<c\&comma;x=x\right]\right]$

$R≔\mathrm{PolynomialRing}\left(\left[x\&comma;a\&comma;b\right]\right)$

$R≔\mathrm{polynomial\_ring}$

$\mathrm{cad}≔\mathrm{CylindricalAlgebraicDecompose}\left(\left[x^2-a\&comma;x+b\right]\&comma;R\&comma;\mathrm{output}=\mathrm{cadcell}\right)$

$\mathrm{cad}≔\left[\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\&comma;\mathrm{cad\_cell}\right]$

$\mathrm{cad}≔\mathrm{CylindricalAlgebraicDecompose}\left(\left[\left[x^2-a=0\&comma;x+b=0\right]\right]\&comma;R\&comma;\mathrm{output}=\mathrm{cadcell}\right)$

$\mathrm{cad}≔\left[\mathrm{cad\_cell}\right]$

$\mathrm{cad}≔\mathrm{CylindricalAlgebraicDecompose}\left(\left[\left[x^2-a=0\&comma;x+b=0\right]\right]\&comma;R\&comma;\mathrm{output}='\mathrm{rootof}'\right)$

$\mathrm{cad}≔\left[\left[b=b\&comma;a=b^2\&comma;x=-b\right]\right]$

$\mathrm{cad}≔\mathrm{CylindricalAlgebraicDecompose}\left(\left[x-a\right]\&comma;R\&comma;\mathrm{output}='\mathrm{rootof}'\right)$

$\mathrm{cad}≔\left[\left[b=b\&comma;a=a\&comma;x<a\right]\&comma;\left[b=b\&comma;a=a\&comma;x=a\right]\&comma;\left[b=b\&comma;a=a\&comma;a<x\right]\right]$

$\mathrm{cad}≔\mathrm{CylindricalAlgebraicDecompose}\left(\left[\left[0<x-a\right]\right]\&comma;R\&comma;\mathrm{output}='\mathrm{rootof}'\right)$

$\mathrm{cad}≔\left[\left[b=b\&comma;a=a\&comma;a<x\right]\right]$

$\mathrm{cad}≔\mathrm{CylindricalAlgebraicDecompose}\left(\left[x+b\right]\&comma;R\&comma;\mathrm{output}='\mathrm{rootof}'\right)$

$\mathrm{cad}≔\left[\left[b=b\&comma;a=a\&comma;x<-b\right]\&comma;\left[b=b\&comma;a=a\&comma;x=-b\right]\&comma;\left[b=b\&comma;a=a\&comma;-b<x\right]\right]$

$\mathrm{cad}≔\mathrm{CylindricalAlgebraicDecompose}\left(\left[\left[x+b=0\right]\right]\&comma;R\&comma;\mathrm{output}='\mathrm{rootof}'\right)$

$\mathrm{cad}≔\left[\left[b=b\&comma;a=a\&comma;x=-b\right]\right]$

$\mathrm{cad}≔\mathrm{CylindricalAlgebraicDecompose}\left(\left[\left[x+b=0\right]\&comma;\left[0<x-a\right]\right]\&comma;R\&comma;\mathrm{output}='\mathrm{rootof}'\right)$

$\mathrm{cad}≔\left[\left[b=b\&comma;a<-b\&comma;a<x\right]\&comma;\left[b=b\&comma;a=-b\&comma;-b\le x\right]\&comma;\left[b=b\&comma;-b<a\&comma;x=-b\right]\&comma;\left[b=b\&comma;-b<a\&comma;a<x\right]\right]$

$R≔\mathrm{PolynomialRing}\left(\left[y\&comma;x\right]\right)$

$R≔\mathrm{polynomial\_ring}$

$F≔\left[y^2-x\right]$

$F≔\left[y^2-x\right]$

$\mathrm{cad}≔\mathrm{CylindricalAlgebraicDecompose}\left(F\&comma;R\&comma;\mathrm{method}=\mathrm{recursive}\&comma;\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.$

$R≔\mathrm{PolynomialRing}\left(\left[y\&comma;x\right]\right)$

$R≔\mathrm{polynomial\_ring}$

$F≔\left[x^2+y^2-1=0\&comma;y^2-x=0\right]$

$F≔\left[x^2+y^2-1=0\&comma;y^2-x=0\right]$

$\mathrm{cad}≔\mathrm{CylindricalAlgebraicDecompose}\left(F\&comma;R\&comma;\mathrm{optimization}='\mathrm{EC}'\&comma;\mathrm{output}=\mathrm{allcell}\right)\&colon;$

$\mathrm{nops}\left(\mathrm{cad}\right)$

$9$

$\mathrm{cad2}≔\mathrm{CylindricalAlgebraicDecompose}\left(F\&comma;R\&comma;\mathrm{optimization}='\mathrm{false}'\&comma;\mathrm{output}=\mathrm{allcell}\right)\&colon;$

$\mathrm{nops}\left(\mathrm{cad2}\right)$

$53$

The lsas parameter was introduced in Maple 16.

The output option was introduced in Maple 16.

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

The RegularChains[SemiAlgebraicSetTools][CylindricalAlgebraicDecompose] command was updated in Maple 2020.

The method and optimization options were introduced in Maple 2020.

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