Improving the use of equational constraints in cylindrical algebraic decomposition

Research output: Contribution to conferencePaper

17 Citations (Scopus)
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 languageEnglish
Pages165-172
Number of pages8
DOIs
Publication statusPublished - Jul 2015
EventISSAC '15 - 2015 ACM on International Symposium on Symbolic and Algebraic Computation - Bath, UK United Kingdom
Duration: 6 Jul 20159 Jul 2015

Conference

ConferenceISSAC '15 - 2015 ACM on International Symposium on Symbolic and Algebraic Computation
CountryUK United Kingdom
CityBath
Period6/07/159/07/15

Fingerprint

Projection
Decompose
Complexity Analysis
Polynomial
Cell
Demonstrate

Keywords

  • Cylindrical Algebraic Decomposition
  • equational constraint
  • symbolic computation
  • Computer Algebra

Cite this

England, M., Bradford, R., & Davenport, J. H. (2015). Improving the use of equational constraints in cylindrical algebraic decomposition. 165-172. Paper presented at ISSAC '15 - 2015 ACM on International Symposium on Symbolic and Algebraic Computation , Bath, UK United Kingdom. https://doi.org/10.1145/2755996.2756678

Improving the use of equational constraints in cylindrical algebraic decomposition. / England, Matthew; Bradford, Russell; Davenport, James H.

2015. 165-172 Paper presented at ISSAC '15 - 2015 ACM on International Symposium on Symbolic and Algebraic Computation , Bath, UK United Kingdom.

Research output: Contribution to conferencePaper

England, M, Bradford, R & Davenport, JH 2015, 'Improving the use of equational constraints in cylindrical algebraic decomposition' Paper presented at ISSAC '15 - 2015 ACM on International Symposium on Symbolic and Algebraic Computation , Bath, UK United Kingdom, 6/07/15 - 9/07/15, pp. 165-172. https://doi.org/10.1145/2755996.2756678
England M, Bradford R, Davenport JH. Improving the use of equational constraints in cylindrical algebraic decomposition. 2015. Paper presented at ISSAC '15 - 2015 ACM on International Symposium on Symbolic and Algebraic Computation , Bath, UK United Kingdom. https://doi.org/10.1145/2755996.2756678
England, Matthew ; Bradford, Russell ; Davenport, James H. / Improving the use of equational constraints in cylindrical algebraic decomposition. Paper presented at ISSAC '15 - 2015 ACM on International Symposium on Symbolic and Algebraic Computation , Bath, UK United Kingdom.8 p.
@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 = "7",
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

ER -