TOPICS
Search

Cylindrical Algebraic Decomposition


Define a cell in R^1 as an open interval or a point. A cell in R^(k+1) then has one of two forms,

 {(x,y):x in C, and f(x)<y<g(x)}
(1)

or

 {(x,y):x in C, and y=f(x)},
(2)

where x={x_1,...,x_k}, C is a cell in R^k, f and g are either (1) continuous functions on C such that for some polynomials F and G, F(x,f(x))=0 and G(x,g(x))=0, or (2) +/-infty, and f(x)<g(x) for all x in C.

A cylindrical algebraic decomposition of S subset R^n is a representation of S as a finite union of disjoint cells. Let F be finite set of polynomials in n variables. A cylindrical algebraic decomposition of S subset R^n is said to be F-invariant if each of the polynomials from F has a constant sign on each cell of the decomposition.

The cylindrical algebraic decomposition (CAD) algorithm, given a finite set F of polynomials in n variables, computes an F-invariant cylindrical algebraic decomposition of R^n. Given a logical combination of polynomial equations and inequalities in n real unknowns, one can use the CAD algorithm to find a cylindrical algebraic decomposition of its solution set. For example, the decomposition of

 x^2+y^2+z^2<1
(3)

is given by

 {-1<x<1; -sqrt(1-x^2)<y<sqrt(1-x^2); -sqrt(1-x^2-y^2)<z<sqrt(1-x^2-y^2).
(4)

The command CylindricalDecomposition[ineqs, {x1, x2, ...}] performs cylindrical algebraic decompositions in the Wolfram Language. Although the process is algorithmic, it becomes computationally infeasible for complicated inequalities.


See also

Cylindrical Parts, Generic Cylindrical Algebraic Decomposition, Quantifier Elimination, Tarski's Theorem

This entry contributed by Adam Strzebonski

Explore with Wolfram|Alpha

References

Brown, C. W. "Simple CAD Construction and Its Applications." J. Symbolic Comput. 31, 521-547, 2001.Caviness, B. F. and Johnson, J. R. (Eds.). Quantifier Elimination and Cylindrical Algebraic Decomposition. New York: Springer-Verlag, 1998.Collins, G. E. "Quantifier Elimination for the Elementary Theory of Real Closed Fields by Cylindrical Algebraic Decomposition." Lect. Notes Comput. Sci. 33, 134-183, 1975.Collins, G. E. "Quantifier Elimination by Cylindrical Algebraic Decomposition--Twenty Years of Progress." In Quantifier Elimination and Cylindrical Algebraic Decomposition (Ed. B. F. Caviness and J. R. Johnson). New York: Springer-Verlag, pp. 8-23, 1998.Collins, G. E. and Hong, H. "Partial Cylindrical Algebraic Decomposition for Quantifier Elimination." J. Symb. Comput. 12, 299-328, 1991.Dolzmann, A. and Sturm, T. "Simplification of Quantifier-Free Formulae Over Ordered Fields." J. Symb. Comput. 24, 209-231, 1997.Faugere, J. C.; Gianni, P.; Lazard, D.; and Mora, T. "Efficient Computation of Zero-Dimensional Groebner Bases by Change of Ordering." J. Symb. Comput. 16, 329-344, 1993.Hong, H. "An Improvement of the Projection Operator in Cylindrical Algebraic Decomposition." In ISSAC '90: Proceedings of the International Symposium on Symbolic and Algebraic Computation, August 20-24, 1990, Tokyo, Japan (Ed. S. Watanabe and M. Nagata). New York: ACM Press, pp. 261-264, 1990.Loos, R. and Weispfenning, V. "Applying Lattice Quantifier Elimination." Comput. J. 36, 450-461, 1993.McCallum, S. "Solving Polynomial Strict Inequalities Using Cylindrical Algebraic Decomposition." Comput. J. 36, 432-438, 1993.McCallum, S. "An Improved Projection for Cylindrical Algebraic Decomposition of Three Dimensional Space." J. Symb. Comput. 5, 141-161, 1988.McCallum, S. "An Improved Projection for Cylindrical Algebraic Decomposition." In Quantifier Elimination and Cylindrical Algebraic Decomposition (Ed. B. F. Caviness and J. R. Johnson). New York: Springer-Verlag, pp. 242-268, 1998.McCallum, S. and Collins, G. E. "Local Box Adjacency Algorithms for Cylindrical Algebraic Decompositions." J. Symb. Comput. 33, 321-342, 2002.Strzebonski, A. "An Algorithm for Systems of Strong Polynomial Inequalities." Mathematica J. 4, 74-77, 1994.Strzebonski, A. "A Real Polynomial Decision Algorithm Using Arbitrary-Precision Floating Point Arithmetic." Reliable Comput. 5, 337-346, 1999.Strzebonski, A. "Solving Algebraic Inequalities." Mathematica J. 7, 525-541, 2000.Trott, M. "Polynomials in Inequalities." §1.2.3 in The Mathematica GuideBook for Symbolics. New York: Springer-Verlag, pp. 50-78, 2006. http://www.mathematicaguidebooks.org/.

Referenced on Wolfram|Alpha

Cylindrical Algebraic Decomposition

Cite this as:

Strzebonski, Adam. "Cylindrical Algebraic Decomposition." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/CylindricalAlgebraicDecomposition.html

Subject classifications