Cylindrical algebraic decomposition
In mathematics, cylindrical algebraic decomposition is a notion and an algorithm to compute it, which are fundamental for computer algebra and real algebraic geometry. Given a set S of polynomials in Rn, a cylindrical algebraic decomposition, commonly abbreviated CAD, is a decomposition of Rn into connected semialgebraic sets called cells, on which each polynomial has constant sign, either +, − or 0. For being cylindrical, this decomposition must satisfy the following condition: If 1 ≤ k < n and π is the projection from Rn onto Rn−k consisting in removing the k last coordinates, then for every 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 Rn−k.
Collins' algorithm has a computational complexity 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 over the reals, which has a much better computational complexity than that which results from the original proof of Tarski–Seidenberg theorem. It is efficient enough for being 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.
- 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. ISBN 978-3-540-33098-1; 3-540-33098-4
- Strzebonski, Adam. Cylindrical Algebraic Decomposition from MathWorld.
- Cylindrical Algebraic Decomposition in Planning algorithms by Steven M. LaValle. Accessed 13 July 2007
|This algebra-related article is a stub. You can help Wikipedia by expanding it.|