Truth Table Invariant Cylindrical Algebraic Decomposition by Regular Chains
arXiv:1401.6310 · doi:10.1007/978-3-319-10515-4_4
Abstract
A new algorithm to compute cylindrical algebraic decompositions (CADs) is presented, building on two recent advances. Firstly, the output is truth table invariant (a TTICAD) meaning given formulae have constant truth value on each cell of the decomposition. Secondly, the computation uses regular chains theory to first build a cylindrical decomposition of complex space (CCD) incrementally by polynomial. Significant modification of the regular chains technology was used to achieve the more sophisticated invariance criteria. Experimental results on an implementation in the RegularChains Library for Maple verify that combining these advances gives an algorithm superior to its individual components and competitive with the state of the art.
References in corpus (6)
- Truth Table Invariant 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
- Choosing a variable ordering for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition
- Cylindrical Algebraic Sub-Decompositions
- An Incremental Algorithm for Computing Cylindrical Algebraic Decompositions
Cited by in corpus (20)
- Truth Table Invariant Cylindrical Algebraic Decomposition
- Satisfiability Checking meets Symbolic Computation (Project Paper)
- Improving the use of equational constraints in 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
- 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
- Symbolic Versus Numerical Computation and Visualization of Parameter Regions for Multistationarity of Biological Networks
- Choosing a variable ordering for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition
- 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
- Algorithmically generating new algebraic features of polynomial systems for machine learning
- Need Polynomial Systems be Doubly-exponential?
- Improved cross-validation for classifiers that make algorithmic choices to minimise runtime without compromising output correctness
- Recent Advances in Real Geometric Reasoning
- Quantifier Elimination for Reasoning in Economics
- Formulating problems for real algebraic geometry
- An implementation of Sub-CAD in Maple