Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition
arXiv:1404.6371 · doi:10.1007/978-3-319-08434-3_5
Abstract
Cylindrical algebraic decompositions (CADs) are a key tool for solving problems in real algebraic geometry and beyond. We recently presented a new CAD algorithm combining two advances: truth-table invariance, making the CAD invariant with respect to the truth of logical formulae rather than the signs of polynomials; and CAD construction by regular chains technology, where first a complex decomposition is constructed by refining a tree incrementally by constraint. We here consider how best to formulate problems for input to this algorithm. We focus on a choice (not relevant for other CAD algorithms) about the order in which constraints are presented. We develop new heuristics to help make this choice and thus allow the best use of the algorithm in practice. We also consider other choices of problem formulation for CAD, as discussed in CICM 2013, revisiting these in the context of the new algorithm.
References in corpus (8)
- 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
- Truth Table Invariant Cylindrical Algebraic Decomposition by Regular Chains
- Optimising Problem Formulation for Cylindrical Algebraic Decomposition
- Understanding Branch Cuts of Expressions
- An implementation of CAD in Maple utilising problem formulation, equational constraints and truth-table invariance
- An Incremental Algorithm for Computing Cylindrical Algebraic Decompositions
Cited by in corpus (17)
- Truth Table Invariant Cylindrical Algebraic Decomposition
- Improving the use of equational constraints in cylindrical algebraic decomposition
- Truth Table Invariant Cylindrical Algebraic Decomposition by Regular Chains
- 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
- 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
- Machine Learning for Mathematical Software
- New heuristic to choose a cylindrical algebraic decomposition variable ordering motivated by complexity analysis
- Using the distribution of cells by dimension in a cylindrical algebraic decomposition
- Need Polynomial Systems be Doubly-exponential?
- Recent Advances in Real Geometric Reasoning
- An implementation of Sub-CAD in Maple
- Formulating problems for real algebraic geometry