Optimising Problem Formulation for Cylindrical Algebraic Decomposition
arXiv:1304.7222 · doi:10.1007/978-3-642-39320-4_2
Abstract
Cylindrical algebraic decomposition (CAD) is an important tool for the study of real algebraic geometry with many applications both within mathematics and elsewhere. It is known to have doubly exponential complexity in the number of variables in the worst case, but the actual computation time can vary greatly. It is possible to offer different formulations for a given problem leading to great differences in tractability. In this paper we suggest a new measure for CAD complexity which takes into account the real geometry of the problem. This leads to new heuristics for choosing: the variable ordering for a CAD problem, a designated equational constraint, and formulations for truth-table invariant CADs (TTICADs). We then consider the possibility of using Groebner bases to precondition TTICAD and when such formulations constitute the creation of a new problem.
To appear in: Proceedings of Conferences on Intelligent Computer Mathematics (CICM '13) - Calculemus strand
References in corpus (1)
Cited by in corpus (20)
- Applying machine learning to the problem of choosing a heuristic to select the variable ordering for 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
- Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular 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
- Cylindrical Algebraic Sub-Decompositions
- Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition With Groebner Bases
- Machine Learning for Mathematical Software
- A "Piano Movers" Problem Reformulated
- 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?
- Improved cross-validation for classifiers that make algorithmic choices to minimise runtime without compromising output correctness
- Lessons on Datasets and Paradigms in Machine Learning for Symbolic Computation: A Case Study on CAD
- Recent Advances in Real Geometric Reasoning
- A machine learning based software pipeline to pick the variable ordering for algorithms with polynomial inputs
- A comparison of three heuristics to choose the variable ordering for CAD