Using the Regular Chains Library to build cylindrical algebraic decompositions by projecting and lifting
arXiv:1405.6090 · doi:10.1007/978-3-662-44199-2_69
Abstract
Cylindrical algebraic decomposition (CAD) is an important tool, both for quantifier elimination over the reals and a range of other applications. Traditionally, a CAD is built through a process of projection and lifting to move the problem within Euclidean spaces of changing dimension. Recently, an alternative approach which first decomposes complex space using triangular decomposition before refining to real space has been introduced and implemented within the RegularChains Library of Maple. We here describe a freely available package ProjectionCAD which utilises the routines within the RegularChains Library to build CADs by projection and lifting. We detail how the projection and lifting algorithms were modified to allow this, discuss the motivation and survey the functionality of the package.
References in corpus (9)
- Cylindrical Algebraic Decompositions for Boolean Combinations
- Program Verification in the presence of complex numbers, functions with branch cuts etc
- Truth Table Invariant Cylindrical Algebraic Decomposition by Regular Chains
- Optimising Problem Formulation for Cylindrical Algebraic Decomposition
- Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition
- Cylindrical Algebraic Sub-Decompositions
- Understanding Branch Cuts of Expressions
- An implementation of CAD in Maple utilising problem formulation, equational constraints and truth-table invariance
- An implementation of CAD in Maple utilising McCallum projection
Cited by in corpus (16)
- Truth Table Invariant Cylindrical Algebraic Decomposition
- Truth Table Invariant Cylindrical Algebraic Decomposition by Regular Chains
- Improving the use of equational constraints in cylindrical algebraic decomposition
- Identifying the Parametric Occurrence of Multiple Steady States for some Biological Networks
- Cylindrical Algebraic Decomposition with Equational Constraints
- Using Machine Learning to Improve Cylindrical Algebraic Decomposition
- The complexity of cylindrical algebraic decomposition with respect to polynomial degree
- Comparing machine learning models to choose the variable ordering for cylindrical algebraic decomposition
- Algorithmically generating new algebraic features of polynomial systems for machine learning
- Using the distribution of cells by dimension in a cylindrical algebraic decomposition
- Improved cross-validation for classifiers that make algorithmic choices to minimise runtime without compromising output correctness
- How to flatten a soccer ball
- Recent Advances in Real Geometric Reasoning
- Towards Incremental Cylindrical Algebraic Decomposition in Maple
- Summer Research Report: Towards Incremental Lazard Cylindrical Algebraic Decomposition
- An implementation of Sub-CAD in Maple