Abstract
Cylindrical Algebraic Decomposition (CAD) is a key tool in computational algebraic geometry, best known as a procedure to enable Quantifier Elimination over realclosed fields. However, it has a worst case complexity doubly exponential in the size of the input, which is often encountered in practice. It has been observed that for many problems a change in algorithm settings or problem formulation can cause huge differences in runtime costs, changing problem instances from intractable to easy. A number of heuristics have been developed to help with such choices, but the complicated nature of the geometric relationships involved means these are imperfect and can sometimes make poor choices. We investigate the use of machine learning (specifically support vector machines) to make such choices instead. 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 apply it in two case studies: the first to select between heuristics for choosing a CAD variable ordering; the second to identify when a CAD problem instance would benefit from Gröbner Basis preconditioning. These appear to be the first such applications of machine learning to Symbolic Computation. We demonstrate in both cases that the machine learned choice outperforms human developed heuristics.
Original language  English 

Pages (fromto)  461488 
Number of pages  28 
Journal  Mathematics in Computer Science 
Volume  13 
Issue number  4 
Early online date  3 Apr 2019 
DOIs  
Publication status  Published  Dec 2019 
Bibliographical note
This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.Keywords
 Computer Algebra
 Cylindrical Algebraic Decomposition
 Gröbner Basis
 Machine Learning
 Parameter Selection
 Support Vector Machine
 Symbolic Computation
ASJC Scopus subject areas
 Computational Mathematics
 Computational Theory and Mathematics
 Applied Mathematics
Fingerprint Dive into the research topics of 'Using Machine Learning to Improve Cylindrical Algebraic Decomposition'. Together they form a unique fingerprint.
Profiles

Matthew England
 Faculty Research Centre for Data Science  Associate Professor (Academic)
Person: Teaching and Research