A repository for CAD Examples

Research output: Contribution to journalArticle

  • 7 Citations

Abstract

Cylindrical Algebraic Decomposition (CAD, first introduced in [Col75]) of Euclidean space has become an important tool in mathematics and allows for practical quantifier elimination (QE) over the reals. Much research has gone into improving the projection operator (e.g. [McC85]), the use of partial CADs (e.g. [CH91]), or into alternative algorithms (e.g. [CDM+09]). A problem of fundamentally high complexity (doubly-exponential in the number of variables [DH88]) it can be difficult to judge when a problem will be solved quickly, and easy to write down problems that are computationally infeasible. It can therefore be difficult to test new advances in this field, and even harder to 'experiment' with new ideas. We have created a unified machine-readable repository of examples to be used when considering CADs. This allows for quick access to a host of examples, pulled from various theoretical questions and applications. As well as enabling more efficient research, the creation of the repository has prompted us to look deeper at certain questions related to CADs. The example bank currently facilitates quick input for Maple and Qepcad implementations of CAD and QE. Whilst CAD and QE procedures exist in other software, they are not directly involved in our research.

LanguageEnglish
Pages67-69
Number of pages2
JournalACM Communications in Computer Algebra
Volume46
Issue number3
DOIs
StatusPublished - Jan 2013

Fingerprint

Quantifier Elimination
Repository
Computer aided design
Projection Operator
Maple
Euclidean space
Partial
Decompose
Software
Alternatives
Experiment
Decomposition

Cite this

A repository for CAD Examples. / Bradford, Russell; Davenport, James; Wilson, David.

In: ACM Communications in Computer Algebra, Vol. 46, No. 3, 01.2013, p. 67-69.

Research output: Contribution to journalArticle

@article{a597c11c154d4aafae41f659cea47db6,
title = "A repository for CAD Examples",
abstract = "Cylindrical Algebraic Decomposition (CAD, first introduced in [Col75]) of Euclidean space has become an important tool in mathematics and allows for practical quantifier elimination (QE) over the reals. Much research has gone into improving the projection operator (e.g. [McC85]), the use of partial CADs (e.g. [CH91]), or into alternative algorithms (e.g. [CDM+09]). A problem of fundamentally high complexity (doubly-exponential in the number of variables [DH88]) it can be difficult to judge when a problem will be solved quickly, and easy to write down problems that are computationally infeasible. It can therefore be difficult to test new advances in this field, and even harder to 'experiment' with new ideas. We have created a unified machine-readable repository of examples to be used when considering CADs. This allows for quick access to a host of examples, pulled from various theoretical questions and applications. As well as enabling more efficient research, the creation of the repository has prompted us to look deeper at certain questions related to CADs. The example bank currently facilitates quick input for Maple and Qepcad implementations of CAD and QE. Whilst CAD and QE procedures exist in other software, they are not directly involved in our research.",
author = "Russell Bradford and James Davenport and David Wilson",
year = "2013",
month = "1",
doi = "10.1145/2429135.2429137",
language = "English",
volume = "46",
pages = "67--69",
journal = "ACM Communications in Computer Algebra",
issn = "1932-2232",
publisher = "Association for Computing Machinery",
number = "3",

}

TY - JOUR

T1 - A repository for CAD Examples

AU - Bradford, Russell

AU - Davenport, James

AU - Wilson, David

PY - 2013/1

Y1 - 2013/1

N2 - Cylindrical Algebraic Decomposition (CAD, first introduced in [Col75]) of Euclidean space has become an important tool in mathematics and allows for practical quantifier elimination (QE) over the reals. Much research has gone into improving the projection operator (e.g. [McC85]), the use of partial CADs (e.g. [CH91]), or into alternative algorithms (e.g. [CDM+09]). A problem of fundamentally high complexity (doubly-exponential in the number of variables [DH88]) it can be difficult to judge when a problem will be solved quickly, and easy to write down problems that are computationally infeasible. It can therefore be difficult to test new advances in this field, and even harder to 'experiment' with new ideas. We have created a unified machine-readable repository of examples to be used when considering CADs. This allows for quick access to a host of examples, pulled from various theoretical questions and applications. As well as enabling more efficient research, the creation of the repository has prompted us to look deeper at certain questions related to CADs. The example bank currently facilitates quick input for Maple and Qepcad implementations of CAD and QE. Whilst CAD and QE procedures exist in other software, they are not directly involved in our research.

AB - Cylindrical Algebraic Decomposition (CAD, first introduced in [Col75]) of Euclidean space has become an important tool in mathematics and allows for practical quantifier elimination (QE) over the reals. Much research has gone into improving the projection operator (e.g. [McC85]), the use of partial CADs (e.g. [CH91]), or into alternative algorithms (e.g. [CDM+09]). A problem of fundamentally high complexity (doubly-exponential in the number of variables [DH88]) it can be difficult to judge when a problem will be solved quickly, and easy to write down problems that are computationally infeasible. It can therefore be difficult to test new advances in this field, and even harder to 'experiment' with new ideas. We have created a unified machine-readable repository of examples to be used when considering CADs. This allows for quick access to a host of examples, pulled from various theoretical questions and applications. As well as enabling more efficient research, the creation of the repository has prompted us to look deeper at certain questions related to CADs. The example bank currently facilitates quick input for Maple and Qepcad implementations of CAD and QE. Whilst CAD and QE procedures exist in other software, they are not directly involved in our research.

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

UR - http://www.sigsam.org/cca/

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

U2 - 10.1145/2429135.2429137

DO - 10.1145/2429135.2429137

M3 - Article

VL - 46

SP - 67

EP - 69

JO - ACM Communications in Computer Algebra

T2 - ACM Communications in Computer Algebra

JF - ACM Communications in Computer Algebra

SN - 1932-2232

IS - 3

ER -