Abstract
Polynomial Systems, or at least their algorithms, have the reputation of being doubly-exponential in the number of variables (see the classic papers of Mayr & Mayer from 1982 and Davenport & Heintz from 1988). Nevertheless, the Bezout bound tells us that number of zeros of a zero-dimensional system is singly-exponential in the number of variables. How should this contradiction be reconciled?
We first note that Mayr and Ritscher in 2013 showed the doubly exponential nature of Gröbner bases is with respect to the dimension of the ideal, not the number of variables. This inspires us to consider what can be done for Cylindrical Algebraic Decomposition which produces a doubly-exponential number of polynomials of doubly-exponential degree.
We review work from ISSAC 2015 which showed the number of polynomials could be restricted to doubly-exponential in the (complex) dimension using McCallum’s theory of reduced projection in the presence of equational constraints. We then discuss preliminary results showing the same for the degree of those polynomials. The results are under primitivity assumptions whose importance we illustrate.
| Original language | English |
|---|---|
| Title of host publication | International Congress on Mathematical Software |
| Editors | Gert-Martin Greuel, Thorsten Koch, Peter Paule, Andrew Sommese |
| Place of Publication | Switzerland |
| Publisher | Springer Verlag |
| Pages | 157-164 |
| Number of pages | 8 |
| Volume | 9725 |
| ISBN (Electronic) | 978-3-319-42432-3 |
| ISBN (Print) | 978-3-319-42431-6 |
| DOIs | |
| Publication status | Published - 6 Jul 2016 |
| Event | International Congress on Mathematical Software - Berlin, Germany Duration: 11 Jul 2016 → 14 Jul 2016 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer |
| Volume | 9725 |
| ISSN (Print) | 0302-9743 |
Conference
| Conference | International Congress on Mathematical Software |
|---|---|
| Abbreviated title | ICMS 2016 |
| Country/Territory | Germany |
| City | Berlin |
| Period | 11/07/16 → 14/07/16 |
Bibliographical note
Funded by EU Horizon 2020 FETOPEN-2016-2017-CSA project SC^2 (712689)The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-42432-3_20
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 book series (LNCS, volume 9725)
ISSN 0302-9743
Keywords
- Computer algebra
- Cylindrical algebraic decomposition
- Equational constraint
- Gröbner bases
- Quantifier elimination