A Geometric Approach to Cylindrical Algebraic Decomposition

Abstract

Cylindrical algebraic decomposition is a classical construction in real algebraic geometry. Although there are many algorithms to compute a cylindrical algebraic decomposition, their practical performance is still very limited. In this paper, we revisit this problem from a more geometric perspective, where the construction of cylindrical algebraic decomposition is related to the study of morphisms between real varieties. It is showed that the geometric fiber cardinality (geometric property) decides the existence of semi-algebraic continuous sections (semi-algebraic property). As a result, all equations can be systematically exploited in the projection phase, leading to a new simple algorithm whose efficiency is demonstrated by experimental results.

Minor Revision, 34 Pages. Math. Comp., electronically published on June 3, 2025

References in corpus (6)

• Improving the use of equational constraints in cylindrical algebraic decomposition
• Cylindrical Algebraic Decomposition with Equational Constraints
• Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition With Groebner Bases
• Solving parametric systems of polynomial equations over the reals through Hermite matrices
• Decomposition of polynomial sets into characteristic pairs
• Elementary recursive quantifier elimination based on Thom encoding and sign determination