Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition With Groebner Bases
arXiv:1608.04219 · doi:10.1109/SYNASC.2016.020
Abstract
Cylindrical Algebraic Decomposition (CAD) is a key tool in computational algebraic geometry, particularly for quantifier elimination over real-closed fields. However, it can be expensive, with worst case complexity doubly exponential in the size of the input. Hence it is important to formulate the problem in the best manner for the CAD algorithm. One possibility is to precondition the input polynomials using Groebner Basis (GB) theory. Previous experiments have shown that while this can often be very beneficial to the CAD algorithm, for some problems it can significantly worsen the CAD performance. In the present paper we investigate whether machine learning, specifically a support vector machine (SVM), may be used to identify those CAD problems which benefit from GB preconditioning. We run experiments with over 1000 problems (many times larger than previous studies) and find that the machine learned choice does better than the human-made heuristic.
References in corpus (12)
- 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
- 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
- Improving the use of equational constraints in cylindrical algebraic decomposition
- Optimising Problem Formulation for Cylindrical Algebraic Decomposition
- Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition
- The complexity of cylindrical algebraic decomposition with respect to polynomial degree
- Choosing a variable ordering for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition
- Constructing Fewer Open Cells by GCD Computation in CAD Projection
- Need Polynomial Systems be Doubly-exponential?
Cited by in corpus (7)
- 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
- Machine Learning for Mathematical Software
- 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
- A Geometric Approach to Cylindrical Algebraic Decomposition