CylindricalAlgebraicDecompose - Maple Help

QuantifierElimination

 CylindricalAlgebraicDecompose
 produce the full CAD for a set of polynomials, or the set of polynomials associated to a Tarski formula

 Calling Sequence CylindricalAlgebraicDecompose( A, E, opts )

Parameters

 A - a list or set of polynomials, or a list or set of relations on polynomials, or a full real Tarski formula, or a single polynomial or relation to produce the CAD for. All such polynomials passed in A are interpreted as inequations, unless they appear as equations in a Tarski formula, whereby they are interpreted as equational constraints E - (optional) a polynomial, an equation, or a list or set of such to be used as equational constraints for the produced CAD opts - core keyword options for cylindrical algebraic decomposition (see QuantifierElimination options)

Returns

Description

 • 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.

Examples

 > $\mathrm{with}\left(\mathrm{QuantifierElimination}\right)$
 $\left[{\mathrm{CylindricalAlgebraicDecompose}}{,}{\mathrm{DeleteFormula}}{,}{\mathrm{InsertFormula}}{,}{\mathrm{PartialCylindricalAlgebraicDecompose}}{,}{\mathrm{QuantifierEliminate}}{,}{\mathrm{QuantifierTools}}\right]$ (1)
 > $A≔\left\{{x}^{2}+{y}^{2}-2,x-3\right\}$
 ${A}{≔}\left\{{x}{-}{3}{,}{{x}}^{{2}}{+}{{y}}^{{2}}{-}{2}\right\}$ (2)
 > $C≔\mathrm{CylindricalAlgebraicDecompose}\left(A\right)$
 ${C}{≔}{\mathrm{CADData for set of polynomials in \left\{y, x\right\}}}$ (3)

Examine the leaf cells for the CAD of polynomials in A:

 > $\mathrm{GetLeafCells}\left(C\right)$
 $\left[{\mathrm{Level 2 CADCell with local description 3 < x and local sample point x = 4}}{,}{\mathrm{Level 2 CADCell with local description x = 3 and local sample point x = 3}}{,}{\mathrm{Level 2 CADCell with local description x < 3 and local sample point x = 2}}{,}{\mathrm{Level 2 CADCell with local description 3 < x and local sample point x = 4}}{,}{\mathrm{Level 2 CADCell with local description x = 3 and local sample point x = 3}}{,}{\mathrm{Level 2 CADCell with local description And\left(RootOf\left(_Z^2+y^2-2,index = real\left[1\right]\right) < x,x < 3\right) and local sample point x = 1}}{,}{\mathrm{Level 2 CADCell with local description x = RootOf\left(_Z^2+y^2-2,index = real\left[1\right]\right) and local sample point x = 0}}{,}{\mathrm{Level 2 CADCell with local description x < RootOf\left(_Z^2+y^2-2,index = real\left[1\right]\right) and local sample point x = -1}}{,}{\mathrm{Level 2 CADCell with local description 3 < x and local sample point x = 4}}{,}{\mathrm{Level 2 CADCell with local description x = 3 and local sample point x = 3}}{,}{\mathrm{Level 2 CADCell with local description And\left(RootOf\left(_Z^2+y^2-2,index = real\left[2\right]\right) < x,x < 3\right) and local sample point x = 2}}{,}{\mathrm{Level 2 CADCell with local description x = RootOf\left(_Z^2+y^2-2,index = real\left[2\right]\right) and local sample point x = RootOf\left(_Z^2-2,208701085205324515393/147573952589676412928 .. 417402170410649030813/295147905179352825856\right)}}{,}{\mathrm{Level 2 CADCell with local description And\left(RootOf\left(_Z^2+y^2-2,index = real\left[1\right]\right) < x,x < RootOf\left(_Z^2+y^2-2,index = real\left[2\right]\right)\right) and local sample point x = 0}}{,}{\mathrm{Level 2 CADCell with local description x = RootOf\left(_Z^2+y^2-2,index = real\left[1\right]\right) and local sample point x = RootOf\left(_Z^2-2,-796131459065725/562949953421312 .. -1592262918131423/1125899906842624\right)}}{,}{\mathrm{Level 2 CADCell with local description x < RootOf\left(_Z^2+y^2-2,index = real\left[1\right]\right) and local sample point x = -3}}{,}{\mathrm{Level 2 CADCell with local description 3 < x and local sample point x = 4}}{,}{\mathrm{Level 2 CADCell with local description x = 3 and local sample point x = 3}}{,}{\mathrm{Level 2 CADCell with local description And\left(RootOf\left(_Z^2+y^2-2,index = real\left[1\right]\right) < x,x < 3\right) and local sample point x = 1}}{,}{\mathrm{Level 2 CADCell with local description x = RootOf\left(_Z^2+y^2-2,index = real\left[1\right]\right) and local sample point x = 0}}{,}{\mathrm{Level 2 CADCell with local description x < RootOf\left(_Z^2+y^2-2,index = real\left[1\right]\right) and local sample point x = -1}}{,}{\mathrm{Level 2 CADCell with local description 3 < x and local sample point x = 4}}{,}{\mathrm{Level 2 CADCell with local description x = 3 and local sample point x = 3}}{,}{\mathrm{Level 2 CADCell with local description x < 3 and local sample point x = 2}}\right]$ (4)

Examine the number leaf cells for the CAD of the formula F:

 > $F≔\mathrm{And}\left({x}^{2}+{y}^{2}-{z}^{2}+2<0,y
 ${F}{≔}{{x}}^{{2}}{+}{{y}}^{{2}}{-}{{z}}^{{2}}{<}{-2}{\wedge }{y}{<}{z}{\wedge }{x}{<}{y}$ (5)
 > $C≔\mathrm{CylindricalAlgebraicDecompose}\left(F\right)$
 ${C}{≔}{\mathrm{CADData for set of polynomials in \left\{z, x, y\right\}}}$ (6)
 > $\mathrm{NumberOfLeafCells}\left(C\right)$
 ${287}$ (7)

Get the sample point for a cell of C:

 > $\mathrm{GetSamplePoint}\left({\mathrm{GetLeafCells}\left(C\right)}_{1}\right)$
 $\left[{z}{=}{3}{,}{x}{=}{4}{,}{y}{=}{5}\right]$ (8)

Compatibility

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