Lazard-style CAD and Equational Constraints

James Harold Davenport; Akshar Sajive Nair; Gregory Kumar Sankaran; Ali Kemal Uncu

doi:10.1145/3597066.3597090

Lazard-style CAD and Equational Constraints

James Harold Davenport, Akshar Sajive Nair, Gregory Kumar Sankaran, Ali Kemal Uncu

Austrian Academy of Sciences

Research output: Chapter or section in a book/report/conference proceeding › Chapter in a published conference proceeding

3 Citations (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 language	English
Title of host publication	ISSAC 2023 - Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation
Editors	Gabriela Jeronimo
Publisher	Association for Computing Machinery
Pages	218-226
Number of pages	9
ISBN (Electronic)	9798400700392
DOIs	https://doi.org/10.1145/3597066.3597090
Publication status	Published - 24 Jul 2023
Event	48th International Symposium on Symbolic and Algebraic Computation, ISSAC 2023 - Tromso, Norway Duration: 24 Jul 2023 → 27 Jul 2023

Publication series

Name	ACM International Conference Proceeding Series

Conference

Conference	48th International Symposium on Symbolic and Algebraic Computation, ISSAC 2023
Country/Territory	Norway
City	Tromso
Period	24/07/23 → 27/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

Access to Document

10.1145/3597066.3597090Licence: CC BY-ND

Cite this

Davenport, J. H., Nair, A. S., Sankaran, G. K., & Uncu, A. K. (2023). Lazard-style CAD and Equational Constraints. In G. Jeronimo (Ed.), ISSAC 2023 - Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation (pp. 218-226). (ACM International Conference Proceeding Series). Association for Computing Machinery. https://doi.org/10.1145/3597066.3597090

Lazard-style CAD and Equational Constraints. / Davenport, James Harold; Nair, Akshar Sajive; Sankaran, Gregory Kumar et al.
ISSAC 2023 - Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation. ed. / Gabriela Jeronimo. Association for Computing Machinery, 2023. p. 218-226 (ACM International Conference Proceeding Series).

Research output: Chapter or section in a book/report/conference proceeding › Chapter in a published conference proceeding

Davenport, JH, Nair, AS, Sankaran, GK & Uncu, AK 2023, Lazard-style CAD and Equational Constraints. in G Jeronimo (ed.), ISSAC 2023 - Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation. ACM International Conference Proceeding Series, Association for Computing Machinery, pp. 218-226, 48th International Symposium on Symbolic and Algebraic Computation, ISSAC 2023, Tromso, Norway, 24/07/23. https://doi.org/10.1145/3597066.3597090

@inproceedings{e0437e18351a40748c46663f50f3a69a,

title = "Lazard-style CAD and Equational Constraints",

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.",

keywords = "Cylindrical algebraic decomposition, Equational constraints, Lazard projection and lifting",

author = "Davenport, {James Harold} and Nair, {Akshar Sajive} and Sankaran, {Gregory Kumar} and Uncu, {Ali Kemal}",

note = "Funding Information: We acknowledge UKRI EPSRC for their constant support. The second author{\textquoteright}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]. ; 48th International Symposium on Symbolic and Algebraic Computation, ISSAC 2023 ; Conference date: 24-07-2023 Through 27-07-2023",

year = "2023",

month = jul,

day = "24",

doi = "10.1145/3597066.3597090",

language = "English",

series = "ACM International Conference Proceeding Series",

publisher = "Association for Computing Machinery",

pages = "218--226",

editor = "Gabriela Jeronimo",

booktitle = "ISSAC 2023 - Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation",

address = "USA United States",

}

TY - GEN

T1 - Lazard-style CAD and Equational Constraints

AU - Davenport, James Harold

AU - Nair, Akshar Sajive

AU - Sankaran, Gregory Kumar

AU - Uncu, Ali Kemal

N1 - 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].

PY - 2023/7/24

Y1 - 2023/7/24

N2 - 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.

AB - 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.

KW - Cylindrical algebraic decomposition

KW - Equational constraints

KW - Lazard projection and lifting

UR - http://www.scopus.com/inward/record.url?scp=85167799649&partnerID=8YFLogxK

U2 - 10.1145/3597066.3597090

DO - 10.1145/3597066.3597090

M3 - Chapter in a published conference proceeding

AN - SCOPUS:85167799649

T3 - ACM International Conference Proceeding Series

SP - 218

EP - 226

BT - ISSAC 2023 - Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation

A2 - Jeronimo, Gabriela

PB - Association for Computing Machinery

T2 - 48th International Symposium on Symbolic and Algebraic Computation, ISSAC 2023

Y2 - 24 July 2023 through 27 July 2023

ER -

Lazard-style CAD and Equational Constraints

Abstract

Publication series

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Pushing Back the Doubly-Exponential Wall of Cylindrical Algebraic Decomposition

Dataset for Quantifier Elimination and CAD examples in Maple

Cite this

Lazard-style CAD and Equational Constraints

Abstract

Publication series

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Projects

Pushing Back the Doubly-Exponential Wall of Cylindrical Algebraic Decomposition

Datasets

Dataset for Quantifier Elimination and CAD examples in Maple

Cite this