Repository logo
 

Using Machine Learning to Improve Cylindrical Algebraic Decomposition

Published version
Peer-reviewed

Change log

Authors

Huang, Zongyan 
England, Matthew 
Wilson, David 
Davenport, James H 
Paulson, Lawrence C 

Abstract

Cylindrical Algebraic Decomposition (CAD) is a key tool in computational algebraic geometry, best known as a procedure to enable Quantifier Elimination over real-closed 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 Groebner 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.

Description

Keywords

Symbolic Computation, Computer Algebra, Machine Learning, Support Vector Machine, Cylindrical Algebraic Decomposition, Grobner Basis, Parameter Selection

Journal Title

Mathematics in Computer Science

Conference Name

Journal ISSN

1661-8289
1661-8289

Volume Title

Publisher

Springer
Sponsorship
Engineering and Physical Sciences Research Council (EP/I011005/1)
This work was supported by EPSRC grant EP/J003247/1; the European Union’s Horizon 2020 research and innovation programme under grant agreement No 712689 (SC2); and the China Scholarship Council (CSC).