On using bi-equational constraints in CAD construction

Christopher W. Brown*, Scott McCallum

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

21 Citations (Scopus)

Abstract

This paper introduces an improved method for constructing cylindrical algebraic decompositions (CADs) for formulas with two polynomial equations as implied constraints. The fundamental idea is that neither of the varieties of the two polynomials is actually represented by the CAD the method produces, only the variety defined by their common zeros is represented. This allows for a substantially smaller projection factor set, and for a CAD with many fewer cells. In the current theory of CADs, the fundamental object is to decompose n-space into regions in which a polynomial equation is either identically true or identically false. With many polynomials, one seeks a decomposition into regions in which each polynomial equation is identically true or false independently. The results presented here are intended to be the first step in establishing a theory of CADs in which systems of equations are fundamental objects, so that given a system we seek a decomposition into regions in which the system is identically true or false - which means each equation is no longer considered independently. Quantifier elimination problems of this form (systems of equations with side conditions) are quite common, and this approach has the potential to bring large problems of this type into the scope of what can be solved in practice. The special case of formulas containing two polynomial equations as constraints is an important one, but this work is also intended to be extended in the future to the more general case.

Original languageEnglish
Title of host publicationProceedings of the 2005 International Symposium on Symbolic and Algebraic Computation, ISSAC'05
EditorsManuel Kauers
Place of PublicationNew York
PublisherAssociation for Computing Machinery (ACM)
Pages76-83
Number of pages8
ISBN (Print)1595930957, 9781595930958
DOIs
Publication statusPublished - 2005
EventISSAC'05 - 2005 International Symposium on Symbolic and Algebraic Computation - Beijing, China
Duration: 24 Jul 200527 Jul 2005

Other

OtherISSAC'05 - 2005 International Symposium on Symbolic and Algebraic Computation
CountryChina
CityBeijing
Period24/07/0527/07/05

Fingerprint Dive into the research topics of 'On using bi-equational constraints in CAD construction'. Together they form a unique fingerprint.

Cite this