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