restart; with(RegularChains); with(ChainTools); with(MatrixTools); with(ConstructibleSetTools); with(ParametricSystemTools); with(SemiAlgebraicSetTools); with(FastArithmeticTools); Cylindrical Algebraic Decomposition (CAD) is a fundamental and powerful tool for studying systems of equations, inequations and inequalities.
Our algorithm is different from the traditional algorithm of Collins. It first computes a cylindrical decomposition of the complex space, from which a CAD of the real space can be easily extracted. Consider the hyperbola
> 
R := PolynomialRing([y, x]); F := [y*x1];


(1) 
A cylindrical algebraic decomposition adapted to the polynomial can be computed by the command CylindricalAlgebraicDecompose as follows:
> 
outcad := CylindricalAlgebraicDecompose(F, R);


(2) 
The output CAD is described by a nested piecewise function. The outmost piecewise function is a function with three conditions , , and . 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.
One can see that the CAD consists of seven cells.
For example, describes one cell of the CAD, where
represents a sample point in this cell.
This sample point is represented by a regular chain and an isolating box such that inside this box there is one and only one root of this regular chain.
We plot the hyperbola and all the sample points of the CAD adapted to this hyperbola as follows.
> 
with(plots);sp := [[1, 2], [1, 1], [1, 0], [0, 0], [1, 0], [1, 1], [1, 2]];points := pointplot(sp, color = blue);curve := implicitplot([x*y1, x], x = 5 .. 5, y = 5 .. 5, color = [red, black]);display([curve, points]);

