### Abstract

Original language | English |
---|---|

Pages (from-to) | 461-488 |

Number of pages | 28 |

Journal | Mathematics in Computer Science |

Volume | 13 |

Issue number | 4 |

Early online date | 3 Apr 2019 |

DOIs | |

Publication status | Published - 1 Dec 2019 |

### 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

### Cite this

*Mathematics in Computer Science*,

*13*(4), 461-488. https://doi.org/10.1007/s11786-019-00394-8

**Using Machine Learning to Improve Cylindrical Algebraic Decomposition.** / Huang, Zongyan; England, Matthew; Wilson, David; Bridge, James; Davenport, James; Paulson, Lawrence.

Research output: Contribution to journal › Article

*Mathematics in Computer Science*, vol. 13, no. 4, pp. 461-488. https://doi.org/10.1007/s11786-019-00394-8

}

TY - JOUR

T1 - Using Machine Learning to Improve Cylindrical Algebraic Decomposition

AU - Huang, Zongyan

AU - England, Matthew

AU - Wilson, David

AU - Bridge, James

AU - Davenport, James

AU - Paulson, Lawrence

PY - 2019/12/1

Y1 - 2019/12/1

N2 - 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 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.

AB - 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 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.

KW - Computer Algebra

KW - Cylindrical Algebraic Decomposition

KW - Gröbner Basis

KW - Machine Learning

KW - Parameter Selection

KW - Support Vector Machine

KW - Symbolic Computation

UR - http://www.scopus.com/inward/record.url?scp=85069154868&partnerID=8YFLogxK

U2 - 10.1007/s11786-019-00394-8

DO - 10.1007/s11786-019-00394-8

M3 - Article

VL - 13

SP - 461

EP - 488

JO - Mathematics in Computer Science

JF - Mathematics in Computer Science

SN - 1661-8270

IS - 4

ER -