Using the distribution of cells by dimension in a cylindrical algebraic decomposition

D. Wilson; M England; R.J. Bradford; J.H. Davenport

doi:10.1109/SYNASC.2014.15

Using the distribution of cells by dimension in a cylindrical algebraic decomposition

D. Wilson, M England, R.J. Bradford, J.H. Davenport

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

13 Citations (SciVal)

242 Downloads (Pure)

Abstract

We investigate the distribution of cells by dimension in cylindrical algebraic decompositions (CADs). We find that they follow a standard distribution which seems largely independent of the underlying problem or CAD algorithm used. Rather, the distribution is inherent to the cylindrical structure and determined mostly by the number of variables.

This insight is then combined with an algorithm that produces only full-dimensional cells to give an accurate method of predicting the number of cells in a complete CAD. Since constructing only full-dimensional cells is relatively inexpensive (involving no costly algebraic number calculations) this leads to heuristics for helping with various questions of problem formulation for CAD, such as choosing an optimal variable ordering. Our experiments demonstrate that this approach can be highly effective.

Original language	English
Title of host publication	Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), 2014 16th International Symposium on
Publisher	IEEE
Pages	53-60
Number of pages	8
ISBN (Print)	978-1-4799-8447-3
DOIs	https://doi.org/10.1109/SYNASC.2014.15
Publication status	Published - 2014

Keywords

Cylindrical Algebraic Decomposition
problem formulation
heuristic

Access to Document

10.1109/SYNASC.2014.15

SYNASC2014
2014 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works
Accepted author manuscript, 329 KBLicence: Unspecified

Cite this

Using the distribution of cells by dimension in a cylindrical algebraic decomposition. / Wilson, D.; England, M; Bradford, R.J. et al.
Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), 2014 16th International Symposium on. IEEE, 2014. p. 53-60.

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

@inproceedings{3210d7d024814df6a1dbbe2a4e551b84,

title = "Using the distribution of cells by dimension in a cylindrical algebraic decomposition",

abstract = "We investigate the distribution of cells by dimension in cylindrical algebraic decompositions (CADs). We find that they follow a standard distribution which seems largely independent of the underlying problem or CAD algorithm used. Rather, the distribution is inherent to the cylindrical structure and determined mostly by the number of variables.This insight is then combined with an algorithm that produces only full-dimensional cells to give an accurate method of predicting the number of cells in a complete CAD. Since constructing only full-dimensional cells is relatively inexpensive (involving no costly algebraic number calculations) this leads to heuristics for helping with various questions of problem formulation for CAD, such as choosing an optimal variable ordering. Our experiments demonstrate that this approach can be highly effective.",

keywords = "Cylindrical Algebraic Decomposition, problem formulation, heuristic",

author = "D. Wilson and M England and R.J. Bradford and J.H. Davenport",

year = "2014",

doi = "10.1109/SYNASC.2014.15",

language = "English",

isbn = "978-1-4799-8447-3",

pages = "53--60",

booktitle = "Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), 2014 16th International Symposium on",

publisher = "IEEE",

address = "USA United States",

}

TY - GEN

T1 - Using the distribution of cells by dimension in a cylindrical algebraic decomposition

AU - Wilson, D.

AU - England, M

AU - Bradford, R.J.

AU - Davenport, J.H.

PY - 2014

Y1 - 2014

N2 - We investigate the distribution of cells by dimension in cylindrical algebraic decompositions (CADs). We find that they follow a standard distribution which seems largely independent of the underlying problem or CAD algorithm used. Rather, the distribution is inherent to the cylindrical structure and determined mostly by the number of variables.This insight is then combined with an algorithm that produces only full-dimensional cells to give an accurate method of predicting the number of cells in a complete CAD. Since constructing only full-dimensional cells is relatively inexpensive (involving no costly algebraic number calculations) this leads to heuristics for helping with various questions of problem formulation for CAD, such as choosing an optimal variable ordering. Our experiments demonstrate that this approach can be highly effective.

AB - We investigate the distribution of cells by dimension in cylindrical algebraic decompositions (CADs). We find that they follow a standard distribution which seems largely independent of the underlying problem or CAD algorithm used. Rather, the distribution is inherent to the cylindrical structure and determined mostly by the number of variables.This insight is then combined with an algorithm that produces only full-dimensional cells to give an accurate method of predicting the number of cells in a complete CAD. Since constructing only full-dimensional cells is relatively inexpensive (involving no costly algebraic number calculations) this leads to heuristics for helping with various questions of problem formulation for CAD, such as choosing an optimal variable ordering. Our experiments demonstrate that this approach can be highly effective.

KW - Cylindrical Algebraic Decomposition

KW - problem formulation

KW - heuristic

UR - http://dx.doi.org/10.1109/SYNASC.2014.15

UR - http://synasc.ro/2014/

U2 - 10.1109/SYNASC.2014.15

DO - 10.1109/SYNASC.2014.15

M3 - Chapter in a published conference proceeding

SN - 978-1-4799-8447-3

SP - 53

EP - 60

BT - Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), 2014 16th International Symposium on

PB - IEEE

ER -

Using the distribution of cells by dimension in a cylindrical algebraic decomposition

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Real Geometry and Connectedness via Triangular Description

Cite this

Using the distribution of cells by dimension in a cylindrical algebraic decomposition

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Projects

Real Geometry and Connectedness via Triangular Description

Cite this