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 -