Improving the use of equational constraints in cylindrical algebraic decomposition

Research output: Contribution to conferencePaper

19 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

Keywords

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

Fingerprint Dive into the research topics of 'Improving the use of equational constraints in cylindrical algebraic decomposition'. Together they form a unique fingerprint.

  • Projects

  • 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