The Complexity of Cylindrical Algebraic Decomposition with Respect to Polynomial Degree

Matthew England; James H. Davenport

doi:10.1007/978-3-319-45641-6_12

The Complexity of Cylindrical Algebraic Decomposition with Respect to Polynomial Degree

Matthew England, James H. Davenport

University of Bath

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

18 Citations (Scopus)

119 Downloads (Pure)

Abstract

Cylindrical algebraic decomposition (CAD) is an important tool for working with polynomial systems, particularly quantifier elimination. However, it has complexity doubly exponential in the number of variables. The base algorithm can be improved by adapting to take advantage of any equational constraints (ECs): equations logically implied by the input. Intuitively, we expect the double exponent in the complexity to decrease by one for each EC. In ISSAC 2015 the present authors proved this for the factor in the complexity bound dependent on the number of polynomials in the input. However, the other term, that dependent on the degree of the input polynomials, remained unchanged. In the present paper the authors investigate how CAD in the presence of ECs could be further refined using the technology of Gr¨obner Bases to move towards the intuitive bound for polynomial degree.

Original language	English
Title of host publication	Computer Algebra in Scientific Computing
Editors	Vladimir P. Gerdt, Wolfram Koepf, Werner M. Seiler, Evgenii V. Vorozhtsov
Place of Publication	Switzerland
Publisher	Springer Verlag
Pages	172-192
Number of pages	21
ISBN (Electronic)	978-3-319-45641-6
ISBN (Print)	978-3-319-45640-9
DOIs	https://doi.org/10.1007/978-3-319-45641-6_12
Publication status	Published - 9 Sept 2016
Event	International Workshop on Computer Algebra in Scientific Computing - Bucharest, Romania Duration: 19 Sept 2016 → 23 Sept 2016

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Verlag
Volume	9890
ISSN (Print)	0302-9743

Workshop

Workshop	International Workshop on Computer Algebra in Scientific Computing
Country/Territory	Romania
City	Bucharest
Period	19/09/16 → 23/09/16

Bibliographical note

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-45641-6_12

Copyright © and Moral Rights are retained by the author(s) and/ or other copyright owners. A copy can be downloaded for personal non-commercial research or study, without prior permission or charge. This item cannot be reproduced or quoted extensively from without first obtaining permission in writing from the copyright holder(s). The content must not be changed in any way or sold commercially in any format or medium without the formal permission of the copyright holders.

Lecture Notes in Computer Science ISSN 0302-9743

Access to Document

10.1007/978-3-319-45641-6_12

Post-PrintAccepted author manuscript, 862 KB

https://researchportal.bath.ac.uk/en/publications/the-complexity-of-cylindrical-algebraic-decomposition-with-respec

Cite this

The Complexity of Cylindrical Algebraic Decomposition with Respect to Polynomial Degree. / England, Matthew; Davenport, James H.
Computer Algebra in Scientific Computing. ed. / Vladimir P. Gerdt; Wolfram Koepf; Werner M. Seiler; Evgenii V. Vorozhtsov. Switzerland: Springer Verlag, 2016. p. 172-192 (Lecture Notes in Computer Science ; Vol. 9890).

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

England, M & Davenport, JH 2016, The Complexity of Cylindrical Algebraic Decomposition with Respect to Polynomial Degree. in VP Gerdt, W Koepf, WM Seiler & EV Vorozhtsov (eds), Computer Algebra in Scientific Computing. Lecture Notes in Computer Science , vol. 9890, Springer Verlag, Switzerland, pp. 172-192, International Workshop on Computer Algebra in Scientific Computing, Bucharest, Romania, 19/09/16. https://doi.org/10.1007/978-3-319-45641-6_12

@inproceedings{4527e77e7fb3460196865eaab20ff140,

title = "The Complexity of Cylindrical Algebraic Decomposition with Respect to Polynomial Degree",

abstract = "Cylindrical algebraic decomposition (CAD) is an important tool for working with polynomial systems, particularly quantifier elimination. However, it has complexity doubly exponential in the number of variables. The base algorithm can be improved by adapting to take advantage of any equational constraints (ECs): equations logically implied by the input. Intuitively, we expect the double exponent in the complexity to decrease by one for each EC. In ISSAC 2015 the present authors proved this for the factor in the complexity bound dependent on the number of polynomials in the input. However, the other term, that dependent on the degree of the input polynomials, remained unchanged. In the present paper the authors investigate how CAD in the presence of ECs could be further refined using the technology of Gr¨obner Bases to move towards the intuitive bound for polynomial degree.",

author = "Matthew England and Davenport, {James H.}",

note = "The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-45641-6_12 Copyright {\textcopyright} and Moral Rights are retained by the author(s) and/ or other copyright owners. A copy can be downloaded for personal non-commercial research or study, without prior permission or charge. This item cannot be reproduced or quoted extensively from without first obtaining permission in writing from the copyright holder(s). The content must not be changed in any way or sold commercially in any format or medium without the formal permission of the copyright holders. Lecture Notes in Computer Science ISSN 0302-9743 ; International Workshop on Computer Algebra in Scientific Computing ; Conference date: 19-09-2016 Through 23-09-2016",

year = "2016",

month = sep,

day = "9",

doi = "10.1007/978-3-319-45641-6_12",

language = "English",

isbn = "978-3-319-45640-9",

series = "Lecture Notes in Computer Science ",

publisher = "Springer Verlag",

pages = "172--192",

editor = "Gerdt, {Vladimir P.} and Wolfram Koepf and Seiler, {Werner M.} and Vorozhtsov, {Evgenii V.}",

booktitle = "Computer Algebra in Scientific Computing",

address = "Austria",

}

TY - GEN

T1 - The Complexity of Cylindrical Algebraic Decomposition with Respect to Polynomial Degree

AU - England, Matthew

AU - Davenport, James H.

N1 - The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-45641-6_12 Copyright © and Moral Rights are retained by the author(s) and/ or other copyright owners. A copy can be downloaded for personal non-commercial research or study, without prior permission or charge. This item cannot be reproduced or quoted extensively from without first obtaining permission in writing from the copyright holder(s). The content must not be changed in any way or sold commercially in any format or medium without the formal permission of the copyright holders. Lecture Notes in Computer Science ISSN 0302-9743

PY - 2016/9/9

Y1 - 2016/9/9

N2 - Cylindrical algebraic decomposition (CAD) is an important tool for working with polynomial systems, particularly quantifier elimination. However, it has complexity doubly exponential in the number of variables. The base algorithm can be improved by adapting to take advantage of any equational constraints (ECs): equations logically implied by the input. Intuitively, we expect the double exponent in the complexity to decrease by one for each EC. In ISSAC 2015 the present authors proved this for the factor in the complexity bound dependent on the number of polynomials in the input. However, the other term, that dependent on the degree of the input polynomials, remained unchanged. In the present paper the authors investigate how CAD in the presence of ECs could be further refined using the technology of Gr¨obner Bases to move towards the intuitive bound for polynomial degree.

AB - Cylindrical algebraic decomposition (CAD) is an important tool for working with polynomial systems, particularly quantifier elimination. However, it has complexity doubly exponential in the number of variables. The base algorithm can be improved by adapting to take advantage of any equational constraints (ECs): equations logically implied by the input. Intuitively, we expect the double exponent in the complexity to decrease by one for each EC. In ISSAC 2015 the present authors proved this for the factor in the complexity bound dependent on the number of polynomials in the input. However, the other term, that dependent on the degree of the input polynomials, remained unchanged. In the present paper the authors investigate how CAD in the presence of ECs could be further refined using the technology of Gr¨obner Bases to move towards the intuitive bound for polynomial degree.

U2 - 10.1007/978-3-319-45641-6_12

DO - 10.1007/978-3-319-45641-6_12

M3 - Conference proceeding

SN - 978-3-319-45640-9

T3 - Lecture Notes in Computer Science

SP - 172

EP - 192

BT - Computer Algebra in Scientific Computing

A2 - Gerdt, Vladimir P.

A2 - Koepf, Wolfram

A2 - Seiler, Werner M.

A2 - Vorozhtsov, Evgenii V.

PB - Springer Verlag

CY - Switzerland

T2 - International Workshop on Computer Algebra in Scientific Computing

Y2 - 19 September 2016 through 23 September 2016

ER -

The Complexity of Cylindrical Algebraic Decomposition with Respect to Polynomial Degree

Abstract

Publication series

Workshop

Bibliographical note

Access to Document

Fingerprint

Cite this