Projects per year
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.
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 1923, 2016, Proceedings 
Editors  V. P. Gerdt, W. Koepf, W. M. Seiler, E. V. Vorozhtsov 
Publisher  Springer Verlag 
Pages  172192 
Number of pages  21 
ISBN (Print)  9783319456409 
DOIs  
Publication status  Published  9 Sep 2016 
Publication series
Name  Lecture Notes in Computer Science 

Publisher  Springer 
Volume  9890 
ISSN (Electronic)  16113349 
Keywords
 computer algebra
 cylindrical algebraic decomposition
 equational constraint
 Groebner bases
 quantifier elimination
ASJC Scopus subject areas
 Computational Theory and Mathematics
Fingerprint Dive into the research topics of 'The complexity of cylindrical algebraic decomposition with respect to polynomial degree'. Together they form a unique fingerprint.
Projects
 2 Finished

SCsquare  Satisfiability Checking and Symbolic Computation: uniting two communities to solve real problems
1/07/16 → 31/08/18
Project: EU Commission

Real Geometry and Connectedness via Triangular Description
Davenport, J., Bradford, R., England, M. & Wilson, D.
Engineering and Physical Sciences Research Council
1/10/11 → 31/12/15
Project: Research council
Profiles

James Davenport
 Department of Computer Science  Hebron and Medlock Professor of Information Technology
 EPSRC Centre for Doctoral Training in Statistical Applied Mathematics (SAMBa)
 International Centre for Higher Education Management (ICHEM)
 Institute of Coding
 UKRI CDT in Accountable, Responsible and Transparent AI
Person: Research & Teaching