Inmathematics,cylindrical algebraic decomposition (CAD) is a notion, along with analgorithm to compute it, that is fundamental forcomputer algebra andreal algebraic geometry. Given a setS of polynomials inRn, a cylindrical algebraic decomposition is a decomposition ofRn into connectedsemialgebraic sets calledcells, on which each polynomial has constant sign, either +, − or 0. To becylindrical, this decomposition must satisfy the following condition: If 1 ≤ k < n andπ is the projection fromRn ontoRn−k consisting in removing the lastk coordinates, then for every pair of cellsc andd, one has eitherπ(c) = π(d) orπ(c) ∩ π(d) = ∅. This implies that the images byπ of the cells define a cylindrical decomposition of Rn−k.
The notion was introduced byGeorge E. Collins in 1975, together with analgorithm for computing it.
Collins' algorithm has acomputational complexity that isdouble exponential inn. 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 ofquantifier elimination over the reals that has a much better computational complexity than that resulting from the original proof ofTarski–Seidenberg theorem. It is efficient enough to be implemented on a computer. It is one of the most important algorithms of computationalreal 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.
 | Thisalgebraic geometry–related article is astub. You can help Wikipedia byexpanding it. |