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

David Wilson; Matthew England; Russell Bradford; James H. Davenport

doi:10.1109/SYNASC.2014.15

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

David Wilson, Matthew England, Russell Bradford, James H. Davenport

University of Bath

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

13 Citations (Scopus)

37 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	Proceedings - 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2014
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	53-60
Number of pages	8
ISBN (Electronic)	9781479984480
DOIs	https://doi.org/10.1109/SYNASC.2014.15
Publication status	Published - 5 Feb 2015
Externally published	Yes
Event	16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing - Timisoara, Romania Duration: 22 Sept 2014 → 25 Sept 2014 Conference number: 16

Conference

Conference	16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing
Abbreviated title	SYNASC 2014
Country/Territory	Romania
City	Timisoara
Period	22/09/14 → 25/09/14

Bibliographical note

© 2015 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, 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 component of this work in other works.

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

cell distribution
cylindrical algebraic decomposition
heuristic
problem formulation

ASJC Scopus subject areas

Computational Theory and Mathematics
Theoretical Computer Science
Applied Mathematics

Access to Document

10.1109/SYNASC.2014.15

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

Cite this

Wilson, D., England, M., Bradford, R., & Davenport, J. H. (2015). Using the distribution of cells by dimension in a cylindrical algebraic decomposition. In Proceedings - 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2014 (pp. 53-60). Article 7034665 Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/SYNASC.2014.15

Using the distribution of cells by dimension in a cylindrical algebraic decomposition. / Wilson, David; England, Matthew; Bradford, Russell et al.
Proceedings - 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2014. Institute of Electrical and Electronics Engineers Inc., 2015. p. 53-60 7034665.

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

Wilson, D, England, M, Bradford, R & Davenport, JH 2015, Using the distribution of cells by dimension in a cylindrical algebraic decomposition. in Proceedings - 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2014., 7034665, Institute of Electrical and Electronics Engineers Inc., pp. 53-60, 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, Timisoara, Romania, 22/09/14. https://doi.org/10.1109/SYNASC.2014.15

@inproceedings{dd9d5328cf144e169a01fa43a92fd34b,

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 = "cell distribution, cylindrical algebraic decomposition, heuristic, problem formulation",

author = "David Wilson and Matthew England and Russell Bradford and Davenport, {James H.}",

note = "{\textcopyright} 2015 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, 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 component of this work in other works. 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. ; 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2014 ; Conference date: 22-09-2014 Through 25-09-2014",

year = "2015",

month = feb,

day = "5",

doi = "10.1109/SYNASC.2014.15",

language = "English",

pages = "53--60",

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

publisher = "Institute of Electrical and Electronics Engineers Inc.",

address = "United States",

}

TY - GEN

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

AU - Wilson, David

AU - England, Matthew

AU - Bradford, Russell

AU - Davenport, James H.

N1 - Conference code: 16

PY - 2015/2/5

Y1 - 2015/2/5

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 - cell distribution

KW - cylindrical algebraic decomposition

KW - heuristic

KW - problem formulation

UR - http://www.scopus.com/inward/record.url?scp=84924241086&partnerID=8YFLogxK

U2 - 10.1109/SYNASC.2014.15

DO - 10.1109/SYNASC.2014.15

M3 - Conference proceeding

SP - 53

EP - 60

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

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing

Y2 - 22 September 2014 through 25 September 2014

ER -

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

Abstract

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Matthew England

Cite this

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

Abstract

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Profiles

Matthew England

Cite this