Cylindrical algebraic sub-decompositions

DOI10.1007/S11786-014-0191-ZzbMATH Open1309.68232DBLPjournals/mics/WilsonBDE14arXiv1401.0647OpenAlexW3098379678WikidataQ59399761 ScholiaQ59399761MaRDI QIDQ475412FDOQ475412

David Wilson, James H. Davenport, Matthew England, Russell Bradford

Publication date: 27 November 2014

Published in: Mathematics in Computer Science (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1401.0647

Recommendations

• Partial cylindrical algebraic decomposition for quantifier elimination
• scientific article; zbMATH DE number 1262462
• Cylindrical algebraic decompositions for Boolean combinations
• Optimising problem formulation for cylindrical algebraic decomposition
• scientific article; zbMATH DE number 3880114

zbMATH Keywords

computer algebrareal algebraic geometrysymbolic computationcomplexity analysiscylindrical algebraic decompositionMapleequational constraints

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Semialgebraic sets and related spaces (14P10) Effectivity, complexity and computational aspects of algebraic geometry (14Q20)

Cites Work

• QEPCAD B
• Partial cylindrical algebraic decomposition for quantifier elimination
• Solving systems of strict polynomial inequalities
• Computing cylindrical algebraic decomposition via triangular decomposition
• Title not available (Why is that?)
• Improved projection for cylindrical algebraic decomposition
• Real quantifier elimination is doubly exponential
• Computation with semialgebraic sets represented by cylindrical algebraic formulas
• Cylindrical algebraic decomposition using validated numerics
• On propagation of equational constraints in CAD-based quantifier elimination
• An effective implementation of a symbolic-numeric cylindrical algebraic decomposition for quantifier elimination
• Solving Polynomial Strict Inequalities Using Cylindrical Algebraic Decomposition
• Title not available (Why is that?)
• Cylindrical Algebraic Decomposition I: The Basic Algorithm
• On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
• Algorithmic methods for investigating equilibria in epidemic modeling
• An Incremental Algorithm for Computing Cylindrical Algebraic Decompositions
• Optimising Problem Formulation for Cylindrical Algebraic Decomposition
• Understanding Branch Cuts of Expressions
• MetiTarski: Past and Future
• Cylindrical algebraic decompositions for boolean combinations
• Constructing a single open cell in a cylindrical algebraic decomposition
• A :20piano movers' '
• Efficient projection orders for CAD
• Title not available (Why is that?)
• Geometry of branch cuts
• Solving polynomial systems over semialgebraic sets represented by cylindrical algebraic formulas
• On using bi-equational constraints in CAD construction
• Title not available (Why is that?)
• Truth table invariant cylindrical algebraic decomposition

Cited In (12)

• Using machine learning to improve cylindrical algebraic decomposition
• Cylindrical algebraic decomposition with equational constraints
• On Approximations and Incidence in Cylindrical Algebraic Decompositions
• Deciding the consistency of non-linear real arithmetic constraints with a conflict driven search using cylindrical algebraic coverings
• Recent Advances in Real Geometric Reasoning
• Properness defects and projections and computation of at least one point in each connected component of a real algebraic set
• Identifying the parametric occurrence of multiple steady states for some biological networks
• Constructing a single cell in cylindrical algebraic decomposition
• Need Polynomial Systems Be Doubly-Exponential?
• The Complexity of Cylindrical Algebraic Decomposition with Respect to Polynomial Degree
• An approximate characterisation of the set of feasible trajectories for constrained flat systems
• Truth table invariant cylindrical algebraic decomposition

Uses Software

• Maple
• MetiTarski
• QEPCAD
• BranchCuts

This page was built for publication: Cylindrical algebraic sub-decompositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q475412)