In mathematics, cylindrical algebraic decomposition (CAD) is a notion, and an algorithm to compute it, that are fundamental for computer algebra and real algebraic geometry. Given a set S of polynomials in Rn, a cylindrical algebraic decomposition is a decomposition of Rn 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 Rn onto Rn−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 Rn−k.
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.
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
In mathematics, cylindrical algebraic decomposition (CAD) is a notion, and an algorithm to compute it, that are fundamental for computer algebra and real algebraic geometry. Given a set S of polynomials in Rn, a cylindrical algebraic decomposition is a decomposition of Rn into connected semialgebraic sets called cells, on which each polynomial has constant sign, either +, − or 0.
Le calcul formel, ou parfois calcul symbolique, est le domaine des mathématiques et de l’informatique qui s’intéresse aux algorithmes opérant sur des objets de nature mathématique par le biais de représentations finies et exactes. Ainsi, un nombre entier est représenté de manière finie et exacte par la suite des chiffres de son écriture en base 2. Étant donné les représentations de deux nombres entiers, le calcul formel se pose par exemple la question de calculer celle de leur produit.
En mathématiques, un corps réel clos est un corps totalement ordonnable dont aucune extension algébrique propre n'est totalement ordonnable. Les corps suivants sont réels clos : le corps des réels, le sous-corps des réels algébriques, le corps des réels calculables (au sens de Turing), le corps des , le corps des séries de Puiseux à coefficients réels, tout corps superréel (en particulier tout corps hyperréel).