Cylindrical Algebraic Decomposition¶
Partition real coordinate space into finitely many connected semialgebraic cells that are cylindrically compatible under projection and sign-invariant for a declared polynomial family.
Core Idea¶
Given a finite polynomial set \(P\subset \mathbb{R}[x_1,\ldots,x_n]\) and an ordering of the variables, a cylindrical algebraic decomposition (CAD) partitions \(\mathbb{R}^n\) into finitely many connected semialgebraic cells. Every polynomial in \(P\) has constant sign on each cell, and the cells are cylindrical: projections of two cells onto any lower-dimensional initial coordinate space are either identical or disjoint.
CAD is both the resulting decomposition and a family of algorithms for constructing it. The classical projection-and-lifting method recursively derives lower-dimensional projection polynomials, decomposes the real line, and lifts stacks of sections and sectors over lower-dimensional cells. Sign- or truth-invariance then turns quantified polynomial formulas into finite cellwise decisions.
Scope of Application¶
CAD supports quantifier elimination over real closed fields, satisfiability of polynomial equalities and inequalities, real root classification, theorem proving, control and stability analysis, robot motion planning, and geometric constraint solving. It is especially valuable when the answer must be exact and described by semialgebraic conditions.
The method is limited by cell growth, coefficient growth, algebraic-number costs, and sensitivity to variable ordering and projection choice. Partial, equational-constraint-aware, truth-table-invariant, and problem-specific variants reduce work without erasing the defining cylindrical-cell architecture.
Clarity¶
State the coefficient domain, input formula or polynomial set, variable ordering, projection operator, invariance target, treatment of nullification, cell representation, and whether the output is a full, partial, sign-invariant, or truth-invariant CAD. Distinguish the decomposition from the algorithm and distinguish logical quantifier order from the implementation's coordinate order.
Manages Complexity¶
CAD replaces a continuum of real assignments with finitely many cells on which all relevant sign or truth values are stable. One sample point can therefore represent every point in a cell for the declared decision task. Projection records where behavior can change; lifting reconstructs only the stratified cases that those critical values require. This is a decisive representational compression even when the number of cells is itself large.
Abstract Reasoning¶
- Normalize the polynomial formula and select a variable ordering. 2. Choose a sound projection operator for the desired invariant. 3. Project critical coefficients, discriminants, and resultants into fewer variables. 4. Isolate the roots at the one-dimensional base. 5. Form point sections and open sectors. 6. Lift each lower-dimensional cell by specializing the next-variable polynomials at its sample point. 7. Verify delineability and handle nullification according to the algorithm.
Knowledge Transfer¶
The portable pattern is project the possible boundaries of behavioral change, partition a simpler space, then lift invariant regions back dimension by dimension. It transfers to stratified decision procedures and exact configuration-space reasoning. The proposed immediate parent is Decomposition.
Relationships to Other Abstractions¶
Current abstraction Cylindrical Algebraic Decomposition Domain-specific
Parents (1) — more general patterns this builds on
-
Cylindrical Algebraic Decomposition is a kind of Decomposition Prime
Decomposition is the proposed immediate parent.
Hierarchy path (1) — routes to 1 parentless root
- Cylindrical Algebraic Decomposition → Decomposition
Neighborhood in Abstraction Space¶
Cylindrical Algebraic Decomposition sits in a sparse region of the domain-specific corpus (86th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Algebraic Structures & Symbolic Decomposition (10 abstractions)
Nearest neighbors
- Ternary Quartic — 0.80
- Character Theory — 0.80
- Algebraic number field — 0.80
- Matrix exponential — 0.80
- Galois Theory — 0.80
Computed from structural-signature embeddings · 2026-09-08