Enhancements to Lazard’s method for cylindrical algebraic decomposition

Christopher W. Brown; Scott McCallum

doi:10.1007/978-3-030-60026-6_8

Enhancements to Lazard’s method for cylindrical algebraic decomposition

Christopher W. Brown^*, Scott McCallum

^*Corresponding author for this work

School of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

9 Citations (Scopus)

Abstract

In 1994 Daniel Lazard proposed an improved method for constructing a cylindrical algebraic decomposition (CAD) from a set of polynomials, which recent work has, finally, fully validated. Lazard’s method works for any set of input polynomials, but is less efficient than the method of Brown (2001) which, however, fails for input sets that are not “well-oriented”. The present work improves Lazard’s method so that it is as efficient for well-oriented input as Brown’s method, while retaining its infallibility. Justifying these improvements requires novel and non-trivial mathematics.

Original language	English
Title of host publication	Computer Algebra in Scientific Computing
Subtitle of host publication	22nd International Workshop, CASC 2020, Proceedings
Editors	François Boulier, Matthew England, Timur M. Sadykov, Evgenii V. Vorozhtsov
Place of Publication	Cham, Switzerland
Publisher	Springer, Springer Nature
Pages	129-149
Number of pages	21
ISBN (Electronic)	9783030600266
ISBN (Print)	9783030600259
DOIs	https://doi.org/10.1007/978-3-030-60026-6_8
Publication status	Published - 2020
Event	22nd International Workshop on Computer Algebra in Scientific Computing, CASC 2020 - Linz, Austria Duration: 14 Sept 2020 → 18 Sept 2020

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12291 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	22nd International Workshop on Computer Algebra in Scientific Computing, CASC 2020
Country/Territory	Austria
City	Linz
Period	14/09/20 → 18/09/20

Access to Document

10.1007/978-3-030-60026-6_8

Cite this

Brown, C. W., & McCallum, S. (2020). Enhancements to Lazard’s method for cylindrical algebraic decomposition. In F. Boulier, M. England, T. M. Sadykov, & E. V. Vorozhtsov (Eds.), Computer Algebra in Scientific Computing: 22nd International Workshop, CASC 2020, Proceedings (pp. 129-149). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12291 LNCS). Springer, Springer Nature. https://doi.org/10.1007/978-3-030-60026-6_8

Brown, Christopher W. ; McCallum, Scott. / Enhancements to Lazard’s method for cylindrical algebraic decomposition. Computer Algebra in Scientific Computing: 22nd International Workshop, CASC 2020, Proceedings. editor / François Boulier ; Matthew England ; Timur M. Sadykov ; Evgenii V. Vorozhtsov. Cham, Switzerland : Springer, Springer Nature, 2020. pp. 129-149 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b62cad8492244df085cb058c5dc9aed8,

title = "Enhancements to Lazard{\textquoteright}s method for cylindrical algebraic decomposition",

abstract = "In 1994 Daniel Lazard proposed an improved method for constructing a cylindrical algebraic decomposition (CAD) from a set of polynomials, which recent work has, finally, fully validated. Lazard{\textquoteright}s method works for any set of input polynomials, but is less efficient than the method of Brown (2001) which, however, fails for input sets that are not “well-oriented”. The present work improves Lazard{\textquoteright}s method so that it is as efficient for well-oriented input as Brown{\textquoteright}s method, while retaining its infallibility. Justifying these improvements requires novel and non-trivial mathematics.",

author = "Brown, {Christopher W.} and Scott McCallum",

year = "2020",

doi = "10.1007/978-3-030-60026-6_8",

language = "English",

isbn = "9783030600259",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer, Springer Nature",

pages = "129--149",

editor = "Fran{\c c}ois Boulier and Matthew England and Sadykov, {Timur M.} and Vorozhtsov, {Evgenii V.}",

booktitle = "Computer Algebra in Scientific Computing",

address = "United States",

note = "22nd International Workshop on Computer Algebra in Scientific Computing, CASC 2020 ; Conference date: 14-09-2020 Through 18-09-2020",

}

Brown, CW & McCallum, S 2020, Enhancements to Lazard’s method for cylindrical algebraic decomposition. in F Boulier, M England, TM Sadykov & EV Vorozhtsov (eds), Computer Algebra in Scientific Computing: 22nd International Workshop, CASC 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12291 LNCS, Springer, Springer Nature, Cham, Switzerland, pp. 129-149, 22nd International Workshop on Computer Algebra in Scientific Computing, CASC 2020, Linz, Austria, 14/09/20. https://doi.org/10.1007/978-3-030-60026-6_8

Enhancements to Lazard’s method for cylindrical algebraic decomposition. / Brown, Christopher W.; McCallum, Scott.
Computer Algebra in Scientific Computing: 22nd International Workshop, CASC 2020, Proceedings. ed. / François Boulier; Matthew England; Timur M. Sadykov; Evgenii V. Vorozhtsov. Cham, Switzerland: Springer, Springer Nature, 2020. p. 129-149 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12291 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - Enhancements to Lazard’s method for cylindrical algebraic decomposition

AU - Brown, Christopher W.

AU - McCallum, Scott

PY - 2020

Y1 - 2020

N2 - In 1994 Daniel Lazard proposed an improved method for constructing a cylindrical algebraic decomposition (CAD) from a set of polynomials, which recent work has, finally, fully validated. Lazard’s method works for any set of input polynomials, but is less efficient than the method of Brown (2001) which, however, fails for input sets that are not “well-oriented”. The present work improves Lazard’s method so that it is as efficient for well-oriented input as Brown’s method, while retaining its infallibility. Justifying these improvements requires novel and non-trivial mathematics.

AB - In 1994 Daniel Lazard proposed an improved method for constructing a cylindrical algebraic decomposition (CAD) from a set of polynomials, which recent work has, finally, fully validated. Lazard’s method works for any set of input polynomials, but is less efficient than the method of Brown (2001) which, however, fails for input sets that are not “well-oriented”. The present work improves Lazard’s method so that it is as efficient for well-oriented input as Brown’s method, while retaining its infallibility. Justifying these improvements requires novel and non-trivial mathematics.

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

U2 - 10.1007/978-3-030-60026-6_8

DO - 10.1007/978-3-030-60026-6_8

M3 - Conference proceeding contribution

AN - SCOPUS:85096561616

SN - 9783030600259

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 129

EP - 149

BT - Computer Algebra in Scientific Computing

A2 - Boulier, François

A2 - England, Matthew

A2 - Sadykov, Timur M.

A2 - Vorozhtsov, Evgenii V.

PB - Springer, Springer Nature

CY - Cham, Switzerland

T2 - 22nd International Workshop on Computer Algebra in Scientific Computing, CASC 2020

Y2 - 14 September 2020 through 18 September 2020

ER -

Brown CW, McCallum S. Enhancements to Lazard’s method for cylindrical algebraic decomposition. In Boulier F, England M, Sadykov TM, Vorozhtsov EV, editors, Computer Algebra in Scientific Computing: 22nd International Workshop, CASC 2020, Proceedings. Cham, Switzerland: Springer, Springer Nature. 2020. p. 129-149. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-60026-6_8

Enhancements to Lazard’s method for cylindrical algebraic decomposition

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this