mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, cylindrical algebraic decomposition (CAD) is a notion, along with an

algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...

to compute it, that is fundamental for

computer algebra In mathematics and computer science, computer algebra, also called symbolic computation or algebraic computation, is a scientific area that refers to the study and development of algorithms and software for manipulating expression (mathematics), ...

and real algebraic geometry. Given a set ''S'' of polynomials in R^''n'', a cylindrical algebraic decomposition is a decomposition of R^''n'' into connected semialgebraic sets called ''cells'', on which each polynomial has constant sign, either +, − or 0. To be ''cylindrical'', this decomposition must satisfy the following condition: If 1 ≤ ''k'' < ''n'' and ''π'' is the projection from R^''n'' onto R^{''n''−''k''} consisting in removing the last ''k'' coordinates, then for every pair of cells ''c'' and ''d'', one has either ''π''(''c'') = ''π''(''d'') or ''π''(''c'') ∩ ''π''(''d'') = ∅. This implies that the images by ''π'' of the cells define a cylindrical decomposition of R^{''n''−''k''}. The notion was introduced by

George E. Collins George E. Collins (born on January 10, 1928 in Stuart, Iowa – and died on November 21, 2017 in Madison, Wisconsin) was an American mathematician and computer scientist. He is the inventor of Garbage collection (computer science), garbage collec ...

in 1975, together with an

for computing it. Collins' algorithm has a

computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations ...

that is double exponential in ''n''. This is an upper bound, which is reached on most entries. There are also examples for which the minimal number of cells is doubly exponential, showing that every general algorithm for cylindrical algebraic decomposition has a double exponential complexity. CAD provides an effective version of

quantifier elimination Quantifier elimination is a concept of simplification used in mathematical logic, model theory, and theoretical computer science. Informally, a quantified statement "\exists x such that ..." can be viewed as a question "When is there an x such ...

over the reals that has a much better computational complexity than that resulting from the original proof of Tarski–Seidenberg theorem. It is efficient enough to be implemented on a computer. It is one of the most important algorithms of computational real algebraic geometry. Searching to improve Collins' algorithm, or to provide algorithms that have a better complexity for subproblems of general interest, is an active field of research.

Implementations

Mathematica Wolfram (previously known as Mathematica and Wolfram Mathematica) is a software system with built-in libraries for several areas of technical computing that allows machine learning, statistics, symbolic computation, data manipulation, network ...

CylindricalDecomposition

* ttp://redlog.eu/ redlog* Maple
The RegularChains Library
an

References

*Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise Algorithms in real algebraic geometry. Second edition. Algorithms and Computation in Mathematics, 10. Springer-Verlag, Berlin, 2006. x+662 pp. ; 3-540-33098-4 *Strzebonski, Adam.

' from

MathWorld ''MathWorld'' is an online mathematics reference work, created and largely written by Eric W. Weisstein. It is sponsored by and licensed to Wolfram Research, Inc. and was partially funded by the National Science Foundation's National Science ...

.
Cylindrical Algebraic Decomposition
in Chapter 6 ("Combinatorial Motion Planning") of ''Planning algorithms'' by Steven M. LaValle. Accessed 8 February 2023 *Caviness, Bob; Johnson, Jeremy
Quantifier Elimination and Cylindrical Algebraic Decomposition
Texts and Monographs in Symbolic Computation. Springer-Verlag, Berlin, 1998. *Collins, George E.: Quantifier elimination for the elementary theory of real closed fields by cylindrical algebraic decomposition, Second GI Conf. Automata Theory and Formal Languages, Springer LNCS 33, 1975. *Davenport, James H.; Heintz, Joos: Real quantifier elimination is doubly exponential, Journal of Symbolic Computation, 1988. Volume 5, Issues 1–2, ISSN 0747-7171, Computer algebra Real algebraic geometry Polynomials category:Quantifier (logic) {{algebraic-geometry-stub