Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition

Abstract

Cylindrical algebraic decomposition(CAD) is a key tool in computational algebraic geometry, particularly for quantifier elimination over real-closed fields. When using CAD, there is often a choice for the ordering placed on the variables. This can be important, with some problems infeasible with one variable ordering but easy with another. Machine learning is the process of fitting a computer model to a complex function based on properties learned from measured data. In this paper we use machine learning (specifically a support vector machine) to select between heuristics for choosing a variable ordering, outperforming each of the separate heuristics.

arXiv comment16 pages

References in corpus (4)

• Machine Learning in Automated Text Categorization
• Cylindrical Algebraic Decompositions for Boolean Combinations
• Program Verification in the presence of complex numbers, functions with branch cuts etc
• Optimising Problem Formulation for Cylindrical Algebraic Decomposition

Cited by in corpus (19)

• Improving the use of equational constraints in cylindrical algebraic decomposition
• The complexity of cylindrical algebraic decomposition with respect to polynomial degree
• Symbolic Versus Numerical Computation and Visualization of Parameter Regions for Multistationarity of Biological Networks
• 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
• Machine Learning for Mathematical Software
• TheoryGuru: A Mathematica Package to apply Quantifier Elimination
• 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
• Need Polynomial Systems be Doubly-exponential?
• Recent Advances in Real Geometric Reasoning
• A machine learning based software pipeline to pick the variable ordering for algorithms with polynomial inputs
• Lessons on Datasets and Paradigms in Machine Learning for Symbolic Computation: A Case Study on CAD
• Generating Elementary Integrable Expressions
• Good pivots for small sparse matrices
• A comparison of three heuristics to choose the variable ordering for CAD
• Learning a performance metric of Buchberger's algorithm
• On Minimal and Minimum Cylindrical Algebraic Decompositions
• Recent Developments in Real Quantifier Elimination and Cylindrical Algebraic Decomposition