In mathematics, cylindrical algebraic decomposition (CAD) is a notion, along with an algorithm to compute it, that is fundamental for computer algebra and real algebraic geometry. Given a set S of polynomials in R<sup>n</sup>, a cylindrical algebraic decomposition is a decomposition of R<sup>n</sup> 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<sup>n</sup> onto R<sup>nâÂÂk</sup> 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<sup>nâÂÂk</sup>.
The notion was introduced by George E. Collins in 1975, together with an algorithm for computing it.
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 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.