A comparison of three heuristics to choose the variable ordering for CAD

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

doi:10.1145/2733693.2733706

A comparison of three heuristics to choose the variable ordering for CAD

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

Research output: Chapter or section in a book/report/conference proceeding › Chapter in a published conference proceeding

1 Citation (SciVal)

140 Downloads (Pure)

Abstract

Cylindrical algebraic decomposition (CAD) is a key tool for problems in real algebraic geometry and beyond. When using CAD there is often a choice over the variable ordering to use, with some problems infeasible in one ordering but simple in another. Here we discuss a recent experiment comparing three heuristics for making this choice on thousands of examples.

Original language	English
Title of host publication	ACM Communications in Computer Algebra
Editors	E. Zima, M. Caboara, J-G. Dumas, L. Gonzalez-Vega, M. Wester, L. Zhi
Place of Publication	New York, U. S. A.
Publisher	Association for Computing Machinery
Pages	121-123
Number of pages	3
Volume	48
Edition	3-4
DOIs	https://doi.org/10.1145/2733693.2733706
Publication status	Published - Feb 2015

Access to Document

10.1145/2733693.2733706

HEWDP14
© ACM, YYYY. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM Communications in Computer Algebra, 48, 3/4, (2014)} http://doi.acm.org/10.1145/2733693.2733706
Accepted author manuscript, 193 KB

Cite this

Huang, Z., England, M., Wilson, D., Davenport, J. H., & Paulson, L. C. (2015). A comparison of three heuristics to choose the variable ordering for CAD. In E. Zima, M. Caboara, J.-G. Dumas, L. Gonzalez-Vega, M. Wester, & L. Zhi (Eds.), ACM Communications in Computer Algebra (3-4 ed., Vol. 48, pp. 121-123). Association for Computing Machinery. https://doi.org/10.1145/2733693.2733706

A comparison of three heuristics to choose the variable ordering for CAD. / Huang, Zongyan; England, Matthew; Wilson, David et al.
ACM Communications in Computer Algebra. ed. / E. Zima; M. Caboara; J-G. Dumas; L. Gonzalez-Vega; M. Wester; L. Zhi. Vol. 48 3-4. ed. New York, U. S. A.: Association for Computing Machinery, 2015. p. 121-123.

Research output: Chapter or section in a book/report/conference proceeding › Chapter in a published conference proceeding

Huang, Z, England, M, Wilson, D, Davenport, JH & Paulson, LC 2015, A comparison of three heuristics to choose the variable ordering for CAD. in E Zima, M Caboara, J-G Dumas, L Gonzalez-Vega, M Wester & L Zhi (eds), ACM Communications in Computer Algebra. 3-4 edn, vol. 48, Association for Computing Machinery, New York, U. S. A., pp. 121-123. https://doi.org/10.1145/2733693.2733706

@inproceedings{6f08a48784084ac483fbd41d94a969cc,

title = "A comparison of three heuristics to choose the variable ordering for CAD",

abstract = "Cylindrical algebraic decomposition (CAD) is a key tool for problems in real algebraic geometry and beyond. When using CAD there is often a choice over the variable ordering to use, with some problems infeasible in one ordering but simple in another. Here we discuss a recent experiment comparing three heuristics for making this choice on thousands of examples.",

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

year = "2015",

month = feb,

doi = "10.1145/2733693.2733706",

language = "English",

volume = "48",

pages = "121--123",

editor = "E. Zima and M. Caboara and J-G. Dumas and L. Gonzalez-Vega and M. Wester and L. Zhi",

booktitle = "ACM Communications in Computer Algebra",

publisher = "Association for Computing Machinery",

address = "USA United States",

edition = "3-4",

}

TY - GEN

T1 - A comparison of three heuristics to choose the variable ordering for CAD

AU - Huang, Zongyan

AU - England, Matthew

AU - Wilson, David

AU - Davenport, James H.

AU - Paulson, Lawrence C.

PY - 2015/2

Y1 - 2015/2

N2 - Cylindrical algebraic decomposition (CAD) is a key tool for problems in real algebraic geometry and beyond. When using CAD there is often a choice over the variable ordering to use, with some problems infeasible in one ordering but simple in another. Here we discuss a recent experiment comparing three heuristics for making this choice on thousands of examples.

AB - Cylindrical algebraic decomposition (CAD) is a key tool for problems in real algebraic geometry and beyond. When using CAD there is often a choice over the variable ordering to use, with some problems infeasible in one ordering but simple in another. Here we discuss a recent experiment comparing three heuristics for making this choice on thousands of examples.

UR - http://dx.doi.org/10.1145/2733693.2733706

U2 - 10.1145/2733693.2733706

DO - 10.1145/2733693.2733706

M3 - Chapter in a published conference proceeding

VL - 48

SP - 121

EP - 123

BT - ACM Communications in Computer Algebra

A2 - Zima, E.

A2 - Caboara, M.

A2 - Dumas, J-G.

A2 - Gonzalez-Vega, L.

A2 - Wester, M.

A2 - Zhi, L.

PB - Association for Computing Machinery

CY - New York, U. S. A.

ER -

A comparison of three heuristics to choose the variable ordering for CAD

Abstract

Access to Document

Other files and links

Fingerprint

Real Geometry and Connectedness via Triangular Description

Cite this

A comparison of three heuristics to choose the variable ordering for CAD

Abstract

Access to Document

Other files and links

Fingerprint

Projects

Real Geometry and Connectedness via Triangular Description

Cite this