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

doi:10.1007/978-3-319-08434-3_8

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 proceeding › Conference proceeding › peer-review

45 Citations (Scopus)

43 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 language	English
Title of host publication	Intelligent Computer Mathematics - International Conference, CICM 2014, Proceedings
Editors	Stephen M. Watt, James H. Davenport, Alan P. Sexton, Petr Sojka, Josef Urban
Place of Publication	Cham
Publisher	Springer Verlag
Pages	92-107
Number of pages	16
Volume	8543 LNAI
ISBN (Print)	9783319084336
DOIs	https://doi.org/10.1007/978-3-319-08434-3_8
Publication status	Published - 2014
Externally published	Yes
Event	2014 International Conference on Intelligent Computer Mathematics - Coimbra, Portugal Duration: 7 Jul 2014 → 11 Jul 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8543 LNAI
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Conference

Conference	2014 International Conference on Intelligent Computer Mathematics
Abbreviated title	CICM 2014
Country/Territory	Portugal
City	Coimbra
Period	7/07/14 → 11/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
General Computer Science

Access to Document

10.1007/978-3-319-08434-3_8

Post-PrintAccepted author manuscript, 903 KBLicence: CC BY-NC

Matthew England
- Research Centre for Computational Science and Mathematical Modelling - Centre Director
Person: Professional Services

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). Springer Verlag. https://doi.org/10.1007/978-3-319-08434-3_8

Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition. / Huang, Zongyan; England, Matthew; Wilson, David et al.
Intelligent Computer Mathematics - International Conference, CICM 2014, Proceedings. ed. / Stephen M. Watt; James H. Davenport; Alan P. Sexton; Petr Sojka; Josef Urban. Vol. 8543 LNAI Cham: Springer Verlag, 2014. p. 92-107 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8543 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding › peer-review

Huang, Z, England, M, Wilson, D, Davenport, JH, Paulson, LC & Bridge, J 2014, Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition. in SM Watt, JH Davenport, AP Sexton, P Sojka & J Urban (eds), Intelligent Computer Mathematics - International Conference, CICM 2014, Proceedings. vol. 8543 LNAI, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8543 LNAI, Springer Verlag, Cham, pp. 92-107, 2014 International Conference on Intelligent Computer Mathematics, Coimbra, Portugal, 7/07/14. https://doi.org/10.1007/978-3-319-08434-3_8

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

Huang, Zongyan ; England, Matthew ; Wilson, David et al. / Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition. Intelligent Computer Mathematics - International Conference, CICM 2014, Proceedings. editor / Stephen M. Watt ; James H. Davenport ; Alan P. Sexton ; Petr Sojka ; Josef Urban. Vol. 8543 LNAI Cham : Springer Verlag, 2014. pp. 92-107 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{e48a5e5d2cd24e7a96944d26146cff53,

title = "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.",

keywords = "cylindrical algebraic decomposition, machine learning, problem formulation, support vector machine, symbolic computation",

author = "Zongyan Huang and Matthew England and David Wilson and Davenport, {James H.} and Paulson, {Lawrence C.} and James Bridge",

note = "The final publication is available at Springer via http://dx.doi.org/[10.1007/978-3- 319-08434-3_8 Copyright {\textcopyright} 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.; 2014 International Conference on Intelligent Computer Mathematics, CICM 2014 ; Conference date: 07-07-2014 Through 11-07-2014",

year = "2014",

doi = "10.1007/978-3-319-08434-3_8",

language = "English",

isbn = "9783319084336",

volume = "8543 LNAI",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "92--107",

editor = "Watt, {Stephen M.} and Davenport, {James H.} and Sexton, {Alan P.} and Petr Sojka and Josef Urban",

booktitle = "Intelligent Computer Mathematics - International Conference, CICM 2014, Proceedings",

address = "Austria",

}

TY - GEN

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

AU - Huang, Zongyan

AU - England, Matthew

AU - Wilson, David

AU - Davenport, James H.

AU - Paulson, Lawrence C.

AU - Bridge, James

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

PY - 2014

Y1 - 2014

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

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

KW - cylindrical algebraic decomposition

KW - machine learning

KW - problem formulation

KW - support vector machine

KW - symbolic computation

U2 - 10.1007/978-3-319-08434-3_8

DO - 10.1007/978-3-319-08434-3_8

M3 - Conference proceeding

AN - SCOPUS:84904172375

SN - 9783319084336

VL - 8543 LNAI

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 92

EP - 107

BT - Intelligent Computer Mathematics - International Conference, CICM 2014, Proceedings

A2 - Watt, Stephen M.

A2 - Davenport, James H.

A2 - Sexton, Alan P.

A2 - Sojka, Petr

A2 - Urban, Josef

PB - Springer Verlag

CY - Cham

T2 - 2014 International Conference on Intelligent Computer Mathematics

Y2 - 7 July 2014 through 11 July 2014

ER -

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

Abstract

Publication series

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Profiles

Matthew England

Cite this