Need polynomial systems be doubly-exponential?
From MaRDI portal
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"{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.
Recommendations
- scientific article; zbMATH DE number 4212207
- The complexity of cylindrical algebraic decomposition with respect to polynomial degree
- Doubly-exponential growth of the number of vectors of multiplicities for solutions of systems of polynomial
- The complexity of quantifier elimination and cylindrical algebraic decomposition
- Sharper complexity bounds for zero-dimensional Gröbner bases and polynomial system solving
Cites work
- Algorithmic methods for investigating equilibria in epidemic modeling
- An effective implementation of a symbolic-numeric cylindrical algebraic decomposition for quantifier elimination
- Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition
- Bruno Buchberger's PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. Translation from the German
- Computing cylindrical algebraic decomposition via triangular decomposition
- Constructing a single open cell in a cylindrical algebraic decomposition
- Constructing fewer open cells by GCD computation in CAD projection
- Cylindrical Algebraic Decomposition I: The Basic Algorithm
- Cylindrical algebraic decomposition using local projections
- Cylindrical algebraic decomposition using validated numerics
- Cylindrical algebraic decompositions for Boolean combinations
- Cylindrical algebraic sub-decompositions
- Dimension-dependent bounds for Gröbner bases of polynomial ideals
- Explicit factors of some iterated resultants and discriminants
- Factors of iterated resultants and discriminants
- scientific article; zbMATH DE number 3857249 (Why is no real title available?)
- scientific article; zbMATH DE number 1157648 (Why is no real title available?)
- scientific article; zbMATH DE number 1157658 (Why is no real title available?)
- scientific article; zbMATH DE number 2151220 (Why is no real title available?)
- Improved projection for cylindrical algebraic decomposition
- Improving the use of equational constraints in cylindrical algebraic decomposition
- On propagation of equational constraints in CAD-based quantifier elimination
- Optimising problem formulation for cylindrical algebraic decomposition
- Partial cylindrical algebraic decomposition for quantifier elimination
- Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition
- Real quantifier elimination is doubly exponential
- Sharp Effective Nullstellensatz
- Synthesis of optimal numerical algorithms using real quantifier elimination (case study: square root computation)
- The complexity of cylindrical algebraic decomposition with respect to polynomial degree
- The complexity of quantifier elimination and cylindrical algebraic decomposition
- The complexity of the word problems for commutative semigroups and polynomial ideals
- Truth table invariant cylindrical algebraic decomposition
- Truth table invariant cylindrical algebraic decomposition by regular chains
Cited in
(3)
This page was built for publication: Need polynomial systems be doubly-exponential?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2819212)
