A comparison of three heuristics to choose the variable ordering for cylindrical algebraic decomposition

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 cylindrical algebraic decomposition

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

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

38 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
Pages (from-to)	121-123
Number of pages	3
Journal	ACM Communications in Computer Algebra
Volume	48
Issue number	3-4
DOIs	https://doi.org/10.1145/2733693.2733706
Publication status	Published - 5 Feb 2015
Externally published	Yes

ASJC Scopus subject areas

Computational Theory and Mathematics
Computational Mathematics

Access to Document

10.1145/2733693.2733706

Post-PrintAccepted author manuscript, 564 KBLicence: CC BY

http://www.cs.bath.ac.uk/~me350/Conferences/ISSAC2014-Poster.pdf

Cite this

@article{fb19449ffb22459789675cd3d97b328c,

title = "A comparison of three heuristics to choose the variable ordering for cylindrical algebraic decomposition",

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,

day = "5",

doi = "10.1145/2733693.2733706",

language = "English",

volume = "48",

pages = "121--123",

journal = "ACM Communications in Computer Algebra",

issn = "1932-2232",

publisher = "Association for Computing Machinery (ACM)",

number = "3-4",

}

TY - JOUR

T1 - A comparison of three heuristics to choose the variable ordering for cylindrical algebraic decomposition

AU - Huang, Zongyan

AU - England, Matthew

AU - Wilson, David

AU - Davenport, James H.

AU - Paulson, Lawrence C.

PY - 2015/2/5

Y1 - 2015/2/5

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://www.scopus.com/inward/record.url?scp=84922853962&partnerID=8YFLogxK

U2 - 10.1145/2733693.2733706

DO - 10.1145/2733693.2733706

M3 - Article

AN - SCOPUS:84922853962

SN - 1932-2232

VL - 48

SP - 121

EP - 123

JO - ACM Communications in Computer Algebra

JF - ACM Communications in Computer Algebra

IS - 3-4

ER -

A comparison of three heuristics to choose the variable ordering for cylindrical algebraic decomposition

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this