A CADData object that contains data structures for the CAD.

Builds a full Cylindrical Algebraic Decomposition (CAD), (Lazard and) sign invariant for the polynomials according to input. Unlike PartialCylindricalAlgebraicDecompose, this procedure will not attempt any evaluation of truth values and hence no quantifier elimination (QE), although it can accept a (quantified) Tarski formula as input. If quantifiers are included in a formula, they will be ignored.

The method of constructing the CAD is a Lazard projection followed by standard lifting. No strategy for lifting is included, considering the whole CAD must be constructed in all circumstances. If equational constraints are provided via E, then these will be used in a reduced projection operator for the first projection.

If equational constraints can be found in a Tarski formula A, then these will be used in a reduced projection operator if possible.

Information on keyword options for the routine can be found in the help page QuantifierElimination options.

$\mathrm{with}\left(\mathrm{QuantifierElimination}\right)$

$\left[\mathrm{CylindricalAlgebraicDecompose}\,\mathrm{DeleteFormula}\,\mathrm{InsertFormula}\,\mathrm{PartialCylindricalAlgebraicDecompose}\,\mathrm{QuantifierEliminate}\,\mathrm{QuantifierTools}\right]$

$A≔\left\{x-3\,x^2+y^2-2\right\}$

$A≔\left\{x-3\,x^2+y^2-2\right\}$

$C≔\mathrm{CylindricalAlgebraicDecompose}\left(A\right)$

$C≔\left[\begin{array}{lll}\mathrm{Variables}& \=& \left[y\,x\right]\\ \mathrm{Input\; Polynomials}& \=& \left[\begin{array}{cccc}x-3& y^2+7& y^2-2& x^2+y^2-2\end{array}\right]\\ \mathrm{\#\; Cells}& \=& 23\\ \mathrm{Projection\; polynomials\; for\; level\; 1}& \=& \left[\begin{array}{cc}{y}^2+7& y^2-2\end{array}\right]\\ \mathrm{Projection\; polynomials\; for\; level\; 2}& \=& \left[\begin{array}{cc}x-3& x^2+y^2-2\end{array}\right]\end{array}\right.$

$\mathrm{GetCells}\left(C\right)$

$\left[\left[\begin{array}{lll}\mathrm{Description}& \&equals;& \mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;\frac{208701085205324515393}{147573952589676412928}..\frac{417402170410649030813}{295147905179352825856}\right)<y\wedge 3<x\\ \mathrm{Sample\; Point}& \&equals;& \left[y=3\&comma;x=4\right]\\ \mathrm{Index}& \&equals;& \left[5\&comma;3\right]\end{array}\right.\&comma;\left[\begin{array}{lll}\mathrm{Description}& \&equals;& \mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;\frac{208701085205324515393}{147573952589676412928}..\frac{417402170410649030813}{295147905179352825856}\right)<y\wedge x=3\\ \mathrm{Sample\; Point}& \&equals;& \left[y=3\&comma;x=3\right]\\ \mathrm{Index}& \&equals;& \left[5\&comma;2\right]\end{array}\right.\&comma;\left[\begin{array}{lll}\mathrm{Description}& \&equals;& \mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;\frac{208701085205324515393}{147573952589676412928}..\frac{417402170410649030813}{295147905179352825856}\right)<y\wedge x<3\\ \mathrm{Sample\; Point}& \&equals;& \left[y=3\&comma;x=2\right]\\ \mathrm{Index}& \&equals;& \left[5\&comma;1\right]\end{array}\right.\&comma;\left[\begin{array}{lll}\mathrm{Description}& \&equals;& y=\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;\frac{208701085205324515393}{147573952589676412928}..\frac{417402170410649030813}{295147905179352825856}\right)\wedge 3<x\\ \mathrm{Sample\; Point}& \&equals;& \left[y=\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;\frac{208701085205324515393}{147573952589676412928}..\frac{417402170410649030813}{295147905179352825856}\right)\&comma;x=4\right]\\ \mathrm{Index}& \&equals;& \left[4\&comma;5\right]\end{array}\right.\&comma;\left[\begin{array}{lll}\mathrm{Description}& \&equals;& y=\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;\frac{208701085205324515393}{147573952589676412928}..\frac{417402170410649030813}{295147905179352825856}\right)\wedge x=3\\ \mathrm{Sample\; Point}& \&equals;& \left[y=\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;\frac{208701085205324515393}{147573952589676412928}..\frac{417402170410649030813}{295147905179352825856}\right)\&comma;x=3\right]\\ \mathrm{Index}& \&equals;& \left[4\&comma;4\right]\end{array}\right.\&comma;\left[\begin{array}{lll}\mathrm{Description}& \&equals;& y=\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;\frac{208701085205324515393}{147573952589676412928}..\frac{417402170410649030813}{295147905179352825856}\right)\wedge 0<x\wedge x<3\\ \mathrm{Sample\; Point}& \&equals;& \left[y=\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;\frac{208701085205324515393}{147573952589676412928}..\frac{417402170410649030813}{295147905179352825856}\right)\&comma;x=1\right]\\ \mathrm{Index}& \&equals;& \left[4\&comma;3\right]\end{array}\right.\&comma;\left[\begin{array}{lll}\mathrm{Description}& \&equals;& y=\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;\frac{208701085205324515393}{147573952589676412928}..\frac{417402170410649030813}{295147905179352825856}\right)\wedge x=0\\ \mathrm{Sample\; Point}& \&equals;& \left[y=\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;\frac{208701085205324515393}{147573952589676412928}..\frac{417402170410649030813}{295147905179352825856}\right)\&comma;x=0\right]\\ \mathrm{Index}& \&equals;& \left[4\&comma;2\right]\end{array}\right.\&comma;\left[\begin{array}{lll}\mathrm{Description}& \&equals;& y=\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;\frac{208701085205324515393}{147573952589676412928}..\frac{417402170410649030813}{295147905179352825856}\right)\wedge x<0\\ \mathrm{Sample\; Point}& \&equals;& \left[y=\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;\frac{208701085205324515393}{147573952589676412928}..\frac{417402170410649030813}{295147905179352825856}\right)\&comma;x=\mathrm{-1}\right]\\ \mathrm{Index}& \&equals;& \left[4\&comma;1\right]\end{array}\right.\&comma;\left[\begin{array}{lll}\mathrm{Description}& \&equals;& \mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;-\frac{796131459065725}{562949953421312}..-\frac{1592262918131423}{1125899906842624}\right)<y\wedge y<\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;\frac{208701085205324515393}{147573952589676412928}..\frac{417402170410649030813}{295147905179352825856}\right)\wedge 3<x\\ \mathrm{Sample\; Point}& \&equals;& \left[y=0\&comma;x=4\right]\\ \mathrm{Index}& \&equals;& \left[3\&comma;7\right]\end{array}\right.\&comma;\left[\begin{array}{lll}\mathrm{Description}& \&equals;& \mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;-\frac{796131459065725}{562949953421312}..-\frac{1592262918131423}{1125899906842624}\right)<y\wedge y<\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;\frac{208701085205324515393}{147573952589676412928}..\frac{417402170410649030813}{295147905179352825856}\right)\wedge x=3\\ \mathrm{Sample\; Point}& \&equals;& \left[y=0\&comma;x=3\right]\\ \mathrm{Index}& \&equals;& \left[3\&comma;6\right]\end{array}\right.\&comma;\left[\begin{array}{lll}\mathrm{Description}& \&equals;& \mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;-\frac{796131459065725}{562949953421312}..-\frac{1592262918131423}{1125899906842624}\right)<y\wedge y<\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;\frac{208701085205324515393}{147573952589676412928}..\frac{417402170410649030813}{295147905179352825856}\right)\wedge \mathrm{RootOf}\left({\mathrm{\_Z}}^2+y^2-2\&comma;\mathrm{index}={\mathrm{real}}_2\right)<x\wedge x<3\\ \mathrm{Sample\; Point}& \&equals;& \left[y=0\&comma;x=2\right]\\ \mathrm{Index}& \&equals;& \left[3\&comma;5\right]\end{array}\right.\&comma;\left[\begin{array}{lll}\mathrm{Description}& \&equals;& \mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;-\frac{796131459065725}{562949953421312}..-\frac{1592262918131423}{1125899906842624}\right)<y\wedge y<\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;\frac{208701085205324515393}{147573952589676412928}..\frac{417402170410649030813}{295147905179352825856}\right)\wedge x=\mathrm{RootOf}\left({\mathrm{\_Z}}^2+y^2-2\&comma;\mathrm{index}={\mathrm{real}}_2\right)\\ \mathrm{Sample\; Point}& \&equals;& \left[y=0\&comma;x=\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;\frac{208701085205324515393}{147573952589676412928}..\frac{417402170410649030813}{295147905179352825856}\right)\right]\\ \mathrm{Index}& \&equals;& \left[3\&comma;4\right]\end{array}\right.\&comma;\left[\begin{array}{lll}\mathrm{Description}& \&equals;& \mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;-\frac{796131459065725}{562949953421312}..-\frac{1592262918131423}{1125899906842624}\right)<y\wedge y<\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;\frac{208701085205324515393}{147573952589676412928}..\frac{417402170410649030813}{295147905179352825856}\right)\wedge \mathrm{RootOf}\left({\mathrm{\_Z}}^2+y^2-2\&comma;\mathrm{index}={\mathrm{real}}_1\right)<x\wedge x<\mathrm{RootOf}\left({\mathrm{\_Z}}^2+y^2-2\&comma;\mathrm{index}={\mathrm{real}}_2\right)\\ \mathrm{Sample\; Point}& \&equals;& \left[y=0\&comma;x=0\right]\\ \mathrm{Index}& \&equals;& \left[3\&comma;3\right]\end{array}\right.\&comma;\left[\begin{array}{lll}\mathrm{Description}& \&equals;& \mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;-\frac{796131459065725}{562949953421312}..-\frac{1592262918131423}{1125899906842624}\right)<y\wedge y<\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;\frac{208701085205324515393}{147573952589676412928}..\frac{417402170410649030813}{295147905179352825856}\right)\wedge x=\mathrm{RootOf}\left({\mathrm{\_Z}}^2+y^2-2\&comma;\mathrm{index}={\mathrm{real}}_1\right)\\ \mathrm{Sample\; Point}& \&equals;& \left[y=0\&comma;x=\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;-\frac{796131459065725}{562949953421312}..-\frac{1592262918131423}{1125899906842624}\right)\right]\\ \mathrm{Index}& \&equals;& \left[3\&comma;2\right]\end{array}\right.\&comma;\left[\begin{array}{lll}\mathrm{Description}& \&equals;& \mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;-\frac{796131459065725}{562949953421312}..-\frac{1592262918131423}{1125899906842624}\right)<y\wedge y<\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;\frac{208701085205324515393}{147573952589676412928}..\frac{417402170410649030813}{295147905179352825856}\right)\wedge x<\mathrm{RootOf}\left({\mathrm{\_Z}}^2+y^2-2\&comma;\mathrm{index}={\mathrm{real}}_1\right)\\ \mathrm{Sample\; Point}& \&equals;& \left[y=0\&comma;x=\mathrm{-3}\right]\\ \mathrm{Index}& \&equals;& \left[3\&comma;1\right]\end{array}\right.\&comma;\left[\begin{array}{lll}\mathrm{Description}& \&equals;& y=\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;-\frac{796131459065725}{562949953421312}..-\frac{1592262918131423}{1125899906842624}\right)\wedge 3<x\\ \mathrm{Sample\; Point}& \&equals;& \left[y=\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;-\frac{796131459065725}{562949953421312}..-\frac{1592262918131423}{1125899906842624}\right)\&comma;x=4\right]\\ \mathrm{Index}& \&equals;& \left[2\&comma;5\right]\end{array}\right.\&comma;\left[\begin{array}{lll}\mathrm{Description}& \&equals;& y=\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;-\frac{796131459065725}{562949953421312}..-\frac{1592262918131423}{1125899906842624}\right)\wedge x=3\\ \mathrm{Sample\; Point}& \&equals;& \left[y=\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;-\frac{796131459065725}{562949953421312}..-\frac{1592262918131423}{1125899906842624}\right)\&comma;x=3\right]\\ \mathrm{Index}& \&equals;& \left[2\&comma;4\right]\end{array}\right.\&comma;\left[\begin{array}{lll}\mathrm{Description}& \&equals;& y=\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;-\frac{796131459065725}{562949953421312}..-\frac{1592262918131423}{1125899906842624}\right)\wedge 0<x\wedge x<3\\ \mathrm{Sample\; Point}& \&equals;& \left[y=\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;-\frac{796131459065725}{562949953421312}..-\frac{1592262918131423}{1125899906842624}\right)\&comma;x=1\right]\\ \mathrm{Index}& \&equals;& \left[2\&comma;3\right]\end{array}\right.\&comma;\left[\begin{array}{lll}\mathrm{Description}& \&equals;& y=\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;-\frac{796131459065725}{562949953421312}..-\frac{1592262918131423}{1125899906842624}\right)\wedge x=0\\ \mathrm{Sample\; Point}& \&equals;& \left[y=\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;-\frac{796131459065725}{562949953421312}..-\frac{1592262918131423}{1125899906842624}\right)\&comma;x=0\right]\\ \mathrm{Index}& \&equals;& \left[2\&comma;2\right]\end{array}\right.\&comma;\left[\begin{array}{lll}\mathrm{Description}& \&equals;& y=\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;-\frac{796131459065725}{562949953421312}..-\frac{1592262918131423}{1125899906842624}\right)\wedge x<0\\ \mathrm{Sample\; Point}& \&equals;& \left[y=\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;-\frac{796131459065725}{562949953421312}..-\frac{1592262918131423}{1125899906842624}\right)\&comma;x=\mathrm{-1}\right]\\ \mathrm{Index}& \&equals;& \left[2\&comma;1\right]\end{array}\right.\&comma;\left[\begin{array}{lll}\mathrm{Description}& \&equals;& y<\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;-\frac{796131459065725}{562949953421312}..-\frac{1592262918131423}{1125899906842624}\right)\wedge 3<x\\ \mathrm{Sample\; Point}& \&equals;& \left[y=\mathrm{-3}\&comma;x=4\right]\\ \mathrm{Index}& \&equals;& \left[1\&comma;3\right]\end{array}\right.\&comma;\left[\begin{array}{lll}\mathrm{Description}& \&equals;& y<\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;-\frac{796131459065725}{562949953421312}..-\frac{1592262918131423}{1125899906842624}\right)\wedge x=3\\ \mathrm{Sample\; Point}& \&equals;& \left[y=\mathrm{-3}\&comma;x=3\right]\\ \mathrm{Index}& \&equals;& \left[1\&comma;2\right]\end{array}\right.\&comma;\left[\begin{array}{lll}\mathrm{Description}& \&equals;& y<\mathrm{RootOf}\left({\mathrm{\_Z}}^2-2\&comma;-\frac{796131459065725}{562949953421312}..-\frac{1592262918131423}{1125899906842624}\right)\wedge x<3\\ \mathrm{Sample\; Point}& \&equals;& \left[y=\mathrm{-3}\&comma;x=2\right]\\ \mathrm{Index}& \&equals;& \left[1\&comma;1\right]\end{array}\right.\right]$

$F≔\mathrm{And}\left(x^2+y^2-z^2+2<0\&comma;y<z\&comma;x<y\right)$

$F≔x^2+y^2-z^2<\mathrm{-2}\wedge y<z\wedge x<y$

$C≔\mathrm{CylindricalAlgebraicDecompose}\left(F\right)$

$C≔\left[\begin{array}{lll}\mathrm{Variables}& \&equals;& \left[z\&comma;x\&comma;y\right]\\ \mathrm{Input\; Polynomials}& \&equals;& \left[\begin{array}{ccccccccccc}x& z& x-y& x-z& y-z& x^2+2& z^2+2& z^2-2& 2x^2-z^2+2& x^2-z^2+2& x^2+y^2-z^2+2\end{array}\right]\\ \mathrm{\#\; Cells}& \&equals;& 287\\ \mathrm{Projection\; polynomials\; for\; level\; 1}& \&equals;& \left[\begin{array}{ccc}z& z^2+2& z^2-2\end{array}\right]\\ \mathrm{Projection\; polynomials\; for\; level\; 2}& \&equals;& \left[\begin{array}{ccccc}x& x-z& x^2+2& 2x^2-z^2+2& x^2-z^2+2\end{array}\right]\\ \mathrm{Projection\; polynomials\; for\; level\; 3}& \&equals;& \left[\begin{array}{ccc}x-y& y-z& x^2+y^2-z^2+2\end{array}\right]\end{array}\right.$

$\mathrm{NumberOfLeafCells}\left(C\right)$

$287$

$\mathrm{GetSamplePoint}\left(\mathrm{GetCells}\left(C\right)\left[1\right]\right)$

$\left[z=3\&comma;x=4\&comma;y=5\right]$

The QuantifierElimination:-CylindricalAlgebraicDecompose command was introduced in Maple 2023.

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