1 Citation (SciVal)

Abstract

McCallum-style Cylindrical Algebra Decomposition (CAD) is a major improvement on the original Collins version, and has had many subsequent advances, notably for total or partial equational constraints. But it suffers from a problem with nullification. The recently-justified Lazard-style CAD does not have this problem. However, transporting the equational constraints work to Lazard-style does reintroduce nullification issues. This paper explains the problem, and the solutions to it, based on the second author's Ph.D. thesis and the Brown-McCallum improvement to Lazard. With a single equational constraint, we can gain the same improvements in Lazard-style as in McCallum-style CAD. Moreover, our approach does not fail where McCallum would due to nullification. Unsurprisingly, it does not achieve the same level of improvement as it does in the non-nullified cases. We also consider the case of multiple equational constraints.

Original languageEnglish
Title of host publicationISSAC 2023 - Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation
EditorsGabriela Jeronimo
PublisherAssociation for Computing Machinery
Pages218-226
Number of pages9
ISBN (Electronic)9798400700392
DOIs
Publication statusPublished - 24 Jul 2023
Event48th International Symposium on Symbolic and Algebraic Computation, ISSAC 2023 - Tromso, Norway
Duration: 24 Jul 202327 Jul 2023

Publication series

NameACM International Conference Proceeding Series

Conference

Conference48th International Symposium on Symbolic and Algebraic Computation, ISSAC 2023
Country/TerritoryNorway
CityTromso
Period24/07/2327/07/23

Bibliographical note

Funding Information:
We acknowledge UKRI EPSRC for their constant support. The second author’s thesis was supported by EPSRC grant EP/N509589/1. The first and the last authors are partially supported by EPSRC grant EP/T015713/1. The last author also thanks the partial support of Austrian Science Fund FWF grant P34501-N. We are grateful to Chris Brown for explanations of [4].

Keywords

  • Cylindrical algebraic decomposition
  • Equational constraints
  • Lazard projection and lifting

ASJC Scopus subject areas

  • Human-Computer Interaction
  • Computer Networks and Communications
  • Computer Vision and Pattern Recognition
  • Software

Fingerprint

Dive into the research topics of 'Lazard-style CAD and Equational Constraints'. Together they form a unique fingerprint.

Cite this