Enhancements to Lazard’s method for cylindrical algebraic decomposition

Christopher W. Brown*, Scott McCallum

*Corresponding author for this work

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

1 Citation (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 languageEnglish
Title of host publicationComputer Algebra in Scientific Computing
Subtitle of host publication22nd International Workshop, CASC 2020, Proceedings
EditorsFrançois Boulier, Matthew England, Timur M. Sadykov, Evgenii V. Vorozhtsov
Place of PublicationCham, Switzerland
PublisherSpringer, Springer Nature
Pages129-149
Number of pages21
ISBN (Electronic)9783030600266
ISBN (Print)9783030600259
DOIs
Publication statusPublished - 2020
Event22nd International Workshop on Computer Algebra in Scientific Computing, CASC 2020 - Linz, Austria
Duration: 14 Sep 202018 Sep 2020

Publication series

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

Conference

Conference22nd International Workshop on Computer Algebra in Scientific Computing, CASC 2020
CountryAustria
CityLinz
Period14/09/2018/09/20

Fingerprint

Dive into the research topics of 'Enhancements to Lazard’s method for cylindrical algebraic decomposition'. Together they form a unique fingerprint.

Cite this