Improving the use of equational constraints in cylindrical algebraic decomposition

Matthew England; Russell Bradford; James H. Davenport

doi:10.1145/2755996.2756678

Improving the use of equational constraints in cylindrical algebraic decomposition

Matthew England, Russell Bradford, James H. Davenport

Research output: Contribution to conference › Paper

25 Citations (SciVal)

84 Downloads (Pure)

Abstract

When building a cylindrical algebraic decomposition (CAD) savings can be made in the presence of an equational constraint (EC): an equation logically implied by a formula.

The present paper is concerned with how to use multiple ECs, propagating those in the input throughout the projection set. We improve on the approach of McCallum in ISSAC 2001 by using the reduced projection theory to make savings in the lifting phase (both to the polynomials we lift with and the cells lifted over). We demonstrate the benefits with worked examples and a complexity analysis.

Original language	English
Pages	165-172
Number of pages	8
DOIs	https://doi.org/10.1145/2755996.2756678
Publication status	Published - Jul 2015
Event	ISSAC '15 - 2015 ACM on International Symposium on Symbolic and Algebraic Computation - Bath, UK United Kingdom Duration: 6 Jul 2015 → 9 Jul 2015

Conference

Conference	ISSAC '15 - 2015 ACM on International Symposium on Symbolic and Algebraic Computation
Country/Territory	UK United Kingdom
City	Bath
Period	6/07/15 → 9/07/15

Keywords

Cylindrical Algebraic Decomposition
equational constraint
symbolic computation
Computer Algebra

Access to Document

10.1145/2755996.2756678Licence: Unspecified

Real Geometry and Connectedness via Triangular Description
Davenport, J. (PI), Bradford, R. (CoI), England, M. (CoI) & Wilson, D. (CoI)
Engineering and Physical Sciences Research Council
1/10/11 → 31/12/15
Project: Research council

James Davenport
- J.H.Davenportbath.acuk
- Department of Computer Science - Hebron and Medlock Professor of Information Technology
- International Centre for Higher Education Management (ICHEM)
- Institute of Coding
- UKRI CDT in Accountable, Responsible and Transparent AI
- Mathematical Foundations of Computation
Person: Research & Teaching

Dataset supporting the paper: Improving the use of equational constraints in cylindrical algebraic decomposition
England, M. (Creator), Bradford, R. (Creator) & Davenport, J. (Creator), University of Bath, 2015
DOI: 10.15125/BATH-00071
Dataset

Cite this

@conference{59015c9035d44f1bac8d68441acf584b,

title = "Improving the use of equational constraints in cylindrical algebraic decomposition",

abstract = "When building a cylindrical algebraic decomposition (CAD) savings can be made in the presence of an equational constraint (EC): an equation logically implied by a formula. The present paper is concerned with how to use multiple ECs, propagating those in the input throughout the projection set. We improve on the approach of McCallum in ISSAC 2001 by using the reduced projection theory to make savings in the lifting phase (both to the polynomials we lift with and the cells lifted over). We demonstrate the benefits with worked examples and a complexity analysis.",

keywords = "Cylindrical Algebraic Decomposition, equational constraint, symbolic computation, Computer Algebra",

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

year = "2015",

month = jul,

doi = "10.1145/2755996.2756678",

language = "English",

pages = "165--172",

note = "ISSAC '15 - 2015 ACM on International Symposium on Symbolic and Algebraic Computation ; Conference date: 06-07-2015 Through 09-07-2015",

}

TY - CONF

T1 - Improving the use of equational constraints in cylindrical algebraic decomposition

AU - England, Matthew

AU - Bradford, Russell

AU - Davenport, James H.

PY - 2015/7

Y1 - 2015/7

N2 - When building a cylindrical algebraic decomposition (CAD) savings can be made in the presence of an equational constraint (EC): an equation logically implied by a formula. The present paper is concerned with how to use multiple ECs, propagating those in the input throughout the projection set. We improve on the approach of McCallum in ISSAC 2001 by using the reduced projection theory to make savings in the lifting phase (both to the polynomials we lift with and the cells lifted over). We demonstrate the benefits with worked examples and a complexity analysis.

AB - When building a cylindrical algebraic decomposition (CAD) savings can be made in the presence of an equational constraint (EC): an equation logically implied by a formula. The present paper is concerned with how to use multiple ECs, propagating those in the input throughout the projection set. We improve on the approach of McCallum in ISSAC 2001 by using the reduced projection theory to make savings in the lifting phase (both to the polynomials we lift with and the cells lifted over). We demonstrate the benefits with worked examples and a complexity analysis.

KW - Cylindrical Algebraic Decomposition

KW - equational constraint

KW - symbolic computation

KW - Computer Algebra

U2 - 10.1145/2755996.2756678

DO - 10.1145/2755996.2756678

M3 - Paper

SP - 165

EP - 172

T2 - ISSAC '15 - 2015 ACM on International Symposium on Symbolic and Algebraic Computation

Y2 - 6 July 2015 through 9 July 2015

ER -

Improving the use of equational constraints in cylindrical algebraic decomposition

Abstract

Conference

Keywords

Access to Document

Fingerprint

Projects

Real Geometry and Connectedness via Triangular Description

Profiles

James Davenport

Datasets

Dataset supporting the paper: Improving the use of equational constraints in cylindrical algebraic decomposition

Cite this