The complexity of cylindrical algebraic decomposition with respect to polynomial degree
arXiv:1605.02494 · doi:10.1007/978-3-319-45641-6_12
Abstract
Cylindrical algebraic decomposition (CAD) is an important tool for working with polynomial systems, particularly quantifier elimination. However, it has complexity doubly exponential in the number of variables. The base algorithm can be improved by adapting to take advantage of any equational constraints (ECs): equations logically implied by the input. Intuitively, we expect the double exponent in the complexity to decrease by one for each EC. In ISSAC 2015 the present authors proved this for the factor in the complexity bound dependent on the number of polynomials in the input. However, the other term, that dependent on the degree of the input polynomials, remained unchanged. In the present paper the authors investigate how CAD in the presence of ECs could be further refined using the technology of Groebner Bases to move towards the intuitive bound for polynomial degree.
References in corpus (12)
- Truth Table Invariant Cylindrical Algebraic Decomposition
- 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
- Improving the use of equational constraints in cylindrical algebraic decomposition
- Using the Regular Chains Library to build cylindrical algebraic decompositions by projecting and lifting
- Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition
- Speeding up Cylindrical Algebraic Decomposition by Gröbner Bases
- Constructing Fewer Open Cells by GCD Computation in CAD Projection
- Cylindrical Algebraic Sub-Decompositions
- Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition With Groebner Bases
- Using the distribution of cells by dimension in a cylindrical algebraic decomposition
- Need Polynomial Systems be Doubly-exponential?
Cited by in corpus (12)
- 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
- Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition With Groebner Bases
- Machine Learning for Mathematical Software
- Need Polynomial Systems be Doubly-exponential?
- The Potential and Challenges of CAD with Equational Constraints for SC-Square
- Non-linear Real Arithmetic Benchmarks derived from Automated Reasoning in Economics
- Data driven semi-supervised learning
- Safety Certified Cooperative Adaptive Cruise Control under Unreliable Inter-vehicle Communications