### Abstract

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 | |

Publication status | Published - 9 Sep 2016 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer |

Volume | 9890 |

ISSN (Electronic) | 1611-3349 |

### Fingerprint

### Keywords

- computer algebra
- cylindrical algebraic decomposition
- equational constraint
- Groebner bases
- quantifier elimination

### ASJC Scopus subject areas

- Computational Theory and Mathematics

### Cite this

*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.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

*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

}

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 - Conference contribution

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 -