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 in Book/Report/Conference proceedingConference contribution

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.
LanguageEnglish
Title of host publicationACM Communications in Computer Algebra
EditorsE. Zima, M. Caboara, J-G. Dumas, L. Gonzalez-Vega, M. Wester, L. Zhi
Place of PublicationNew York, U. S. A.
PublisherAssociation for Computing Machinery
Pages121-123
Number of pages3
Volume48
Edition3-4
DOIs
StatusPublished - Feb 2015

Fingerprint

Choose
Real Algebraic Geometry
Heuristics
Decompose
Experiment

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). New York, U. S. A.: 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; Davenport, James H.; Paulson, Lawrence C.

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 in Book/Report/Conference proceedingConference contribution

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
Huang Z, England M, Wilson D, Davenport JH, Paulson LC. A comparison of three heuristics to choose the variable ordering for CAD. In Zima E, Caboara M, Dumas J-G, Gonzalez-Vega L, Wester M, Zhi L, editors, ACM Communications in Computer Algebra. 3-4 ed. Vol. 48. New York, U. S. A.: Association for Computing Machinery. 2015. p. 121-123 https://doi.org/10.1145/2733693.2733706
Huang, Zongyan ; England, Matthew ; Wilson, David ; Davenport, James H. ; Paulson, Lawrence C. / A comparison of three heuristics to choose the variable ordering for CAD. ACM Communications in Computer Algebra. editor / 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. pp. 121-123
@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 = "2",
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 - Conference contribution

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 -