Improving the use of equational constraints in cylindrical algebraic decomposition
arXiv:1501.04466 · doi:10.1145/2755996.2756678
Abstract
When building a cylindrical algebraic decomposition (CAD) savings can be made in the presence of an equational constraint (EC): an equation logically implied by a formula. The present paper is concerned with how to use multiple ECs, propagating those in the input throughout the projection set. We improve on the approach of McCallum in ISSAC 2001 by using the reduced projection theory to make savings in the lifting phase (both to the polynomials we lift with and the cells lifted over). We demonstrate the benefits with worked examples and a complexity analysis.
References in corpus (9)
- Truth Table Invariant Cylindrical Algebraic Decomposition
- Cylindrical Algebraic Decompositions for Boolean Combinations
- Program Verification in the presence of complex numbers, functions with branch cuts etc
- Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition
- 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
- Using the Regular Chains Library to build cylindrical algebraic decompositions by projecting and lifting
- Using the distribution of cells by dimension in a cylindrical algebraic decomposition
Cited by in corpus (20)
- Truth Table Invariant Cylindrical Algebraic Decomposition
- Deciding the Consistency of Non-Linear Real Arithmetic Constraints with a Conflict Driven Search Using Cylindrical Algebraic Coverings
- A Case Study on the Parametric Occurrence of Multiple Steady States
- 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
- The multistationarity structure of networks with intermediates and a binomial core network
- Comparing machine learning models to choose the variable ordering for cylindrical algebraic decomposition
- Symbolic Versus Numerical Computation and Visualization of Parameter Regions for Multistationarity of Biological Networks
- Machine Learning for Mathematical Software
- Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition With Groebner Bases
- New heuristic to choose a cylindrical algebraic decomposition variable ordering motivated by complexity analysis
- Algorithmically generating new algebraic features of polynomial systems for machine learning
- Need Polynomial Systems be Doubly-exponential?
- The Potential and Challenges of CAD with Equational Constraints for SC-Square
- Quantifier Elimination for Reasoning in Economics
- Non-linear Real Arithmetic Benchmarks derived from Automated Reasoning in Economics
- Towards Incremental Cylindrical Algebraic Decomposition in Maple
- A Geometric Approach to Cylindrical Algebraic Decomposition