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

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

18 Citations (SciVal)

123 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 Groebner Bases to move towards the intuitive bound for polynomial degree.

Original language	English
Title of host publication	Computer Algebra in Scientific Computing
Subtitle of host publication	18th International Workshop, CASC 2016, Bucharest, Romania, September 19-23, 2016, Proceedings
Editors	V. P. Gerdt, W. Koepf, W. M. Seiler, E. V. Vorozhtsov
Publisher	Springer Verlag
Pages	172-192
Number of pages	21
ISBN (Print)	9783319456409
DOIs	https://doi.org/10.1007/978-3-319-45641-6_12
Publication status	Published - 9 Sept 2016

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	9890
ISSN (Electronic)	1611-3349

Keywords

computer algebra
cylindrical algebraic decomposition
equational constraint
Groebner bases
quantifier elimination

ASJC Scopus subject areas

Computational Theory and Mathematics

Access to Document

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

ED16.PDF
The final publication is available at Springer via 10.1007/978-3-319-45641-6_12
Accepted author manuscript, 404 KBLicence: CC BY-SA

Cite this

England, M., & Davenport, J. H. (2016). The complexity of cylindrical algebraic decomposition with respect to polynomial degree. In V. P. Gerdt, W. Koepf, W. M. Seiler, & E. V. Vorozhtsov (Eds.), Computer Algebra in Scientific Computing: 18th International Workshop, CASC 2016, Bucharest, Romania, September 19-23, 2016, Proceedings (pp. 172-192). (Lecture Notes in Computer Science; Vol. 9890). Springer Verlag. https://doi.org/10.1007/978-3-319-45641-6_12

The complexity of cylindrical algebraic decomposition with respect to polynomial degree. / England, Matthew; Davenport, James H.
Computer Algebra in Scientific Computing: 18th International Workshop, CASC 2016, Bucharest, Romania, September 19-23, 2016, Proceedings. ed. / V. P. Gerdt; W. Koepf; W. M. Seiler; E. V. Vorozhtsov. Springer Verlag, 2016. p. 172-192 (Lecture Notes in Computer Science; Vol. 9890).

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

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: 18th International Workshop, CASC 2016, Bucharest, Romania, September 19-23, 2016, Proceedings. Lecture Notes in Computer Science, vol. 9890, Springer Verlag, pp. 172-192. https://doi.org/10.1007/978-3-319-45641-6_12

England M, Davenport JH. The complexity of cylindrical algebraic decomposition with respect to polynomial degree. In Gerdt VP, Koepf W, Seiler WM, Vorozhtsov EV, editors, Computer Algebra in Scientific Computing: 18th International Workshop, CASC 2016, Bucharest, Romania, September 19-23, 2016, Proceedings. Springer Verlag. 2016. p. 172-192. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-45641-6_12

England, Matthew ; Davenport, James H. / The complexity of cylindrical algebraic decomposition with respect to polynomial degree. Computer Algebra in Scientific Computing: 18th International Workshop, CASC 2016, Bucharest, Romania, September 19-23, 2016, Proceedings. editor / V. P. Gerdt ; W. Koepf ; W. M. Seiler ; E. V. Vorozhtsov. Springer Verlag, 2016. pp. 172-192 (Lecture Notes in Computer Science).

@inproceedings{485ffd9b01b44490afbee4838154c144,

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 Groebner Bases to move towards the intuitive bound for polynomial degree. ",

keywords = "computer algebra, cylindrical algebraic decomposition, equational constraint, Groebner bases, quantifier elimination",

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

year = "2016",

month = sep,

day = "9",

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

language = "English",

isbn = "9783319456409",

series = "Lecture Notes in Computer Science",

publisher = "Springer Verlag",

pages = "172--192",

editor = "Gerdt, {V. P.} and Koepf, {W. } and Seiler, {W. M.} and Vorozhtsov, {E. V.}",

booktitle = "Computer Algebra in Scientific Computing",

}

TY - GEN

T1 - The complexity of cylindrical algebraic decomposition with respect to polynomial degree

AU - England, Matthew

AU - Davenport, James H.

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 Groebner 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 Groebner Bases to move towards the intuitive bound for polynomial degree.

KW - computer algebra

KW - cylindrical algebraic decomposition

KW - equational constraint

KW - Groebner bases

KW - quantifier elimination

UR - http://dx.doi.org/10.1007/978-3-319-45641-6_12

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

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

M3 - Chapter in a published conference proceeding

SN - 9783319456409

T3 - Lecture Notes in Computer Science

SP - 172

EP - 192

BT - Computer Algebra in Scientific Computing

A2 - Gerdt, V. P.

A2 - Koepf, W.

A2 - Seiler, W. M.

A2 - Vorozhtsov, E. V.

PB - Springer Verlag

ER -

The complexity of cylindrical algebraic decomposition with respect to polynomial degree

Abstract

Publication series

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

SC-square - Satisfiability Checking and Symbolic Computation: uniting two communities to solve real problems

Real Geometry and Connectedness via Triangular Description

James Davenport

Cite this

The complexity of cylindrical algebraic decomposition with respect to polynomial degree

Abstract

Publication series

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Projects

SC-square - Satisfiability Checking and Symbolic Computation: uniting two communities to solve real problems

Real Geometry and Connectedness via Triangular Description

Profiles

James Davenport

Cite this