Need Polynomial Systems Be Doubly-Exponential?

James H. Davenport, Matthew England

Research output: Chapter in Book/Report/Conference proceedingChapter

4 Citations (Scopus)
6 Downloads (Pure)

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 languageEnglish
Title of host publicationInternational Congress on Mathematical Software
EditorsGert-Martin Greuel, Thorsten Koch, Peter Paule, Andrew Sommese
Place of PublicationSwitzerland
PublisherSpringer Verlag
Pages157-164
Number of pages8
Volume9725
ISBN (Electronic)978-3-319-42432-3
ISBN (Print)978-3-319-42431-6
DOIs
Publication statusPublished - 6 Jul 2016
EventInternational Congress on Mathematical Software - Berlin, Germany
Duration: 11 Jul 201614 Jul 2016

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9725
ISSN (Print)0302-9743

Conference

ConferenceInternational Congress on Mathematical Software
Abbreviated titleICMS 2016
CountryGermany
CityBerlin
Period11/07/1614/07/16

Fingerprint

Polynomial Systems
Polynomial
Zero-dimensional
Projection
Decompose
Zero

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

Cite this

Davenport, J. H., & England, M. (2016). Need Polynomial Systems Be Doubly-Exponential? In G-M. Greuel, T. Koch, P. Paule, & A. Sommese (Eds.), International Congress on Mathematical Software (Vol. 9725, pp. 157-164). (Lecture Notes in Computer Science ; Vol. 9725). Switzerland: Springer Verlag. https://doi.org/10.1007/978-3-319-42432-3_20

Need Polynomial Systems Be Doubly-Exponential? / Davenport, James H.; England, Matthew.

International Congress on Mathematical Software. ed. / Gert-Martin Greuel; Thorsten Koch; Peter Paule; Andrew Sommese. Vol. 9725 Switzerland : Springer Verlag, 2016. p. 157-164 (Lecture Notes in Computer Science ; Vol. 9725).

Research output: Chapter in Book/Report/Conference proceedingChapter

Davenport, JH & England, M 2016, Need Polynomial Systems Be Doubly-Exponential? in G-M Greuel, T Koch, P Paule & A Sommese (eds), International Congress on Mathematical Software. vol. 9725, Lecture Notes in Computer Science , vol. 9725, Springer Verlag, Switzerland, pp. 157-164, International Congress on Mathematical Software, Berlin, Germany, 11/07/16. https://doi.org/10.1007/978-3-319-42432-3_20
Davenport JH, England M. Need Polynomial Systems Be Doubly-Exponential? In Greuel G-M, Koch T, Paule P, Sommese A, editors, International Congress on Mathematical Software. Vol. 9725. Switzerland: Springer Verlag. 2016. p. 157-164. (Lecture Notes in Computer Science ). https://doi.org/10.1007/978-3-319-42432-3_20
Davenport, James H. ; England, Matthew. / Need Polynomial Systems Be Doubly-Exponential?. International Congress on Mathematical Software. editor / Gert-Martin Greuel ; Thorsten Koch ; Peter Paule ; Andrew Sommese. Vol. 9725 Switzerland : Springer Verlag, 2016. pp. 157-164 (Lecture Notes in Computer Science ).
@inbook{ef41a4295cf74a5eacdba06b429dcaa8,
title = "Need Polynomial Systems Be Doubly-Exponential?",
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{\"o}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.",
keywords = "Computer algebra, Cylindrical algebraic decomposition, Equational constraint, Gr{\"o}bner bases, Quantifier elimination",
author = "Davenport, {James H.} and Matthew England",
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 {\circledC} 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",
year = "2016",
month = "7",
day = "6",
doi = "10.1007/978-3-319-42432-3_20",
language = "English",
isbn = "978-3-319-42431-6",
volume = "9725",
series = "Lecture Notes in Computer Science",
publisher = "Springer Verlag",
pages = "157--164",
editor = "Gert-Martin Greuel and Thorsten Koch and Peter Paule and Andrew Sommese",
booktitle = "International Congress on Mathematical Software",
address = "Austria",

}

TY - CHAP

T1 - Need Polynomial Systems Be Doubly-Exponential?

AU - Davenport, James H.

AU - England, Matthew

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

PY - 2016/7/6

Y1 - 2016/7/6

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

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

KW - Computer algebra

KW - Cylindrical algebraic decomposition

KW - Equational constraint

KW - Gröbner bases

KW - Quantifier elimination

U2 - 10.1007/978-3-319-42432-3_20

DO - 10.1007/978-3-319-42432-3_20

M3 - Chapter

SN - 978-3-319-42431-6

VL - 9725

T3 - Lecture Notes in Computer Science

SP - 157

EP - 164

BT - International Congress on Mathematical Software

A2 - Greuel, Gert-Martin

A2 - Koch, Thorsten

A2 - Paule, Peter

A2 - Sommese, Andrew

PB - Springer Verlag

CY - Switzerland

ER -