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

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

Research output: Chapter in Book/Report/Conference proceedingConference proceeding

27 Citations (Scopus)
8 Downloads (Pure)

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.

Original languageEnglish
Title of host publicationIntelligent Computer Mathematics - International Conference, CICM 2014, Proceedings
EditorsStephen M. Watt, James H. Davenport, Alan P. Sexton, Petr Sojka, Josef Urban
Place of PublicationCham
PublisherSpringer Verlag
Pages92-107
Number of pages16
Volume8543 LNAI
ISBN (Print)9783319084336
DOIs
Publication statusPublished - 2014
Externally publishedYes
Event2014 International Conference on Intelligent Computer Mathematics - Coimbra, Portugal
Duration: 7 Jul 201411 Jul 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8543 LNAI
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference2014 International Conference on Intelligent Computer Mathematics
Abbreviated titleCICM 2014
CountryPortugal
CityCoimbra
Period7/07/1411/07/14

Bibliographical note

The final publication is available at Springer via http://dx.doi.org/[10.1007/978-3-
319-08434-3_8
Copyright © and Moral Rights are retained by the author(s) and/ or other copyright
owners. A copy can be downloaded for personal non-commercial research or study,
without prior permission or charge. This item cannot be reproduced or quoted extensively
from without first obtaining permission in writing from the copyright holder(s). The
content must not be changed in any way or sold commercially in any format or medium
without the formal permission of the copyright holders.

Keywords

  • cylindrical algebraic decomposition
  • machine learning
  • problem formulation
  • support vector machine
  • symbolic computation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition'. Together they form a unique fingerprint.

  • Cite this

    Huang, Z., England, M., Wilson, D., Davenport, J. H., Paulson, L. C., & Bridge, J. (2014). Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition. In S. M. Watt, J. H. Davenport, A. P. Sexton, P. Sojka, & J. Urban (Eds.), Intelligent Computer Mathematics - International Conference, CICM 2014, Proceedings (Vol. 8543 LNAI, pp. 92-107). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8543 LNAI). Cham: Springer Verlag. https://doi.org/10.1007/978-3-319-08434-3_8