Using the distribution of cells by dimension in a cylindrical algebraic decomposition
arXiv:1409.1781 · doi:10.1109/SYNASC.2014.15
Abstract
We investigate the distribution of cells by dimension in cylindrical algebraic decompositions (CADs). We find that they follow a standard distribution which seems largely independent of the underlying problem or CAD algorithm used. Rather, the distribution is inherent to the cylindrical structure and determined mostly by the number of variables. This insight is then combined with an algorithm that produces only full-dimensional cells to give an accurate method of predicting the number of cells in a complete CAD. Since constructing only full-dimensional cells is relatively inexpensive (involving no costly algebraic number calculations) this leads to heuristics for helping with various questions of problem formulation for CAD, such as choosing an optimal variable ordering. Our experiments demonstrate that this approach can be highly effective.
arXiv comment8 pages
References in corpus (9)
- 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
- Choosing a variable ordering for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition
- Cylindrical Algebraic Sub-Decompositions
Cited by in corpus (8)
- Improving the use of equational constraints in cylindrical algebraic decomposition
- 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
- New heuristic to choose a cylindrical algebraic decomposition variable ordering motivated by complexity analysis
- Need Polynomial Systems be Doubly-exponential?
- Lessons on Datasets and Paradigms in Machine Learning for Symbolic Computation: A Case Study on CAD
- Recent Advances in Real Geometric Reasoning