2014/01/31 by D. J. Wilson, R. J. Bradford, J. H. Davenport +1 · 14 citations
Computer Science · Mathematics · #Algebra over a field #Algebraic number #Algebraic variety #Constraint Satisfaction and Optimization #Dimension (graph theory) #Dimension of an algebraic variety #Formal Methods in Verification #Function field of an algebraic variety #Invariant (physics) #Polynomial and algebraic computation #Real algebraic geometry #Variety (cybernetics) #acm:68W30 #cs.SC #math.AG #msc:68W30
paper · pdf · doi:10.1007/s11786-014-0191-z
published in Mathematics in Computer Science 8(2), 263-288 (Birkhäuser) · 26 pages
arxiv created 2014/04/24 · openalex publication_date 2014/06/01 · arxiv updated 2014/06/27 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
Cylindrical algebraic decompositions (CADs) are a key tool in real algebraic geometry, used primarily for eliminating quantifiers over the reals and studying semi-algebraic sets. In this paper we introduce cylindrical algebraic sub-decompositions (sub-CADs), which are subsets of CADs containing all the information needed to specify a solution for a given problem. We define two new types of sub-CAD: variety sub-CADs which are those cells in a CAD lying on a designated variety; and layered sub-CADs which have only those cells of dimension higher than a specified value. We present algorithms to produce these and describe how the two approaches may be combined with each other and the recent theory of truth-table invariant CAD. We give a complexity analysis showing that these techniques can offer substantial theoretical savings, which is supported by experimentation using an implementation in Maple .