Need Polynomial Systems be Doubly-exponential?
arXiv:1605.02912 · doi:10.1007/978-3-319-42432-3_20
Abstract
Polynomial Systems, or at least their algorithms, have the reputation of being doubly-exponential in the number of variables [Mayr and Mayer, 1982], [Davenport and Heintz, 1988]. Nevertheless, the Bezout bound tells us that 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, 2013] shows that 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.
Extended Abstract for ICMS 2016 Presentation. arXiv admin note: text overlap with arXiv:1605.02494
References in corpus (9)
- Truth Table Invariant Cylindrical Algebraic Decomposition
- Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition
- Truth Table Invariant Cylindrical Algebraic Decomposition by Regular Chains
- Improving the use of equational constraints in cylindrical algebraic decomposition
- Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition
- The complexity of cylindrical algebraic decomposition with respect to polynomial degree
- Constructing Fewer Open Cells by GCD Computation in CAD Projection
- Cylindrical Algebraic Sub-Decompositions
- Using the distribution of cells by dimension in a cylindrical algebraic decomposition
Cited by in corpus (5)
- Using Machine Learning to Improve Cylindrical Algebraic Decomposition
- The complexity of cylindrical algebraic decomposition with respect to polynomial degree
- Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition With Groebner Bases
- Lazard-style CAD and Equational Constraints
- The Potential and Challenges of CAD with Equational Constraints for SC-Square