Choosing a variable ordering for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition
arXiv:1405.6094 · doi:10.1007/978-3-662-44199-2_68
Abstract
Cylindrical algebraic decomposition (CAD) is a key tool for solving problems in real algebraic geometry and beyond. In recent years a new approach has been developed, where regular chains technology is used to first build a decomposition in complex space. We consider the latest variant of this which builds the complex decomposition incrementally by polynomial and produces CADs on whose cells a sequence of formulae are truth-invariant. Like all CAD algorithms the user must provide a variable ordering which can have a profound impact on the tractability of a problem. We evaluate existing heuristics to help with the choice for this algorithm, suggest improvements and then derive a new heuristic more closely aligned with the mechanics of the new algorithm.
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
- 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
- Understanding Branch Cuts of Expressions
- A "Piano Movers" Problem Reformulated
- An Incremental Algorithm for Computing Cylindrical Algebraic Decompositions
Cited by in corpus (9)
- Truth Table Invariant Cylindrical Algebraic Decomposition
- Truth Table Invariant Cylindrical Algebraic Decomposition by Regular Chains
- Using Machine Learning to Improve Cylindrical Algebraic Decomposition
- Comparing machine learning models to choose the variable ordering for cylindrical algebraic 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
- Improved cross-validation for classifiers that make algorithmic choices to minimise runtime without compromising output correctness
- Recent Advances in Real Geometric Reasoning
- A machine learning based software pipeline to pick the variable ordering for algorithms with polynomial inputs