Une procédure récursive de projection‑relevage qui partitionne l'espace réel de dimension n en un nombre fini de cellules disposées de façon cylindrique (les projections d'une cellule sont des cellules de la décomposition) sur lesquelles un ensemble fini de polynômes réels a un signe invariant, permettant de décider des requêtes de signe et d'éliminer des quantificateurs réels.

Principe

Projeter les ensembles de polynômes variable par variable pour calculer des polynômes de projection qui captent les conditions limites, puis relever en isolant les racines réelles et construisant des cellules en dimensions supérieures de sorte que chaque cellule soit signe‑invariante pour les polynômes initiaux ; la condition cylindrique garantit un empilement compatible des cellules entre dimensions.

Démonstration

Pour décider ∃x p(x,y)>0, projeter p en x pour obtenir discriminants et résultantes en y, trouver valeurs critiques de y qui partitionnent la droite réelle, puis pour chaque intervalle relever en calculant des valeurs d'échantillonnage en x et des motifs de signes pour déterminer s'il existe x avec p>0 dans cette cellule en y.

Mauvaise application

Utiliser CAD sans discernement sur des problèmes many variables ou de haut degré conduit à des calculs inabordables car la projection engendre de nombreux polynômes ; appliquer CAD à des problèmes complexes (non réels) ou ignorer les garanties d'isolation des racines numériques peut produire des descriptions de cellules incorrectes.

Conséquence

CAD fournit une procédure de décision complète pour les formules du premier ordre sur les corps réels clos : elle donne des décompositions de cellules explicites qui résolvent les quantificateurs et conditions de signe, et peut produire des points d'échantillonnage et des descriptions exactes d'ensembles semi‑algébriques au prix d'une complexité potentiellement élevée.

Inversion

Au lieu d'un CAD complet, on peut utiliser un CAD partiel, la substitution virtuelle ou l'échantillonnage numérique et les méthodes d'intervalles pour répondre à des requêtes spécifiques ; cela remplace la décomposition cylindrique signe‑invariante complète par des alternatives moins coûteuses mais éventuellement incomplètes.

Limite

S'applique aux polynômes à coefficients réels et à l'élimination de quantificateurs réels ; il ne traite pas directement les fonctions transcendantales, les requêtes en variables complexes, et ne se met pas à l'échelle efficacement en présence de nombreuses variables et de hauts degrés sans heuristiques ou réductions spécifiques au problème.

Tension sémantique

CAD garantit l'invariance de signe et la décidabilité pour les problèmes de quantificateurs réels mais souffre d'une complexité pire cas double‑exponentielle ; des méthodes comme les bases de Gröbner ou les solveurs numériques peuvent être plus efficaces pour des tâches algébriques ou approximatives mais manquent de la généralité de CAD pour les quantificateurs réels.

Synthèse

La Décomposition Algébrique Cylindrique est un schéma de projection‑relevage qui produit une partition finie signe‑invariante de l'espace réel en cellules compatibles cylindriquement ; elle transforme des questions de quantificateurs et de signe sur des polynômes en vérifications combinatoires sur cellules et points d'échantillonnage, échangeant décidabilité générale contre coût de calcul élevé.