On the Complexity of Solving Zero-Dimensional Polynomial Systems via Projection
| Autor: | Michael Sagraloff, Cornelius Brand |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
Computer Science - Symbolic Computation FOS: Computer and information sciences Polynomial Computational complexity theory 010102 general mathematics Dimension (graph theory) 010103 numerical & computational mathematics Symbolic Computation (cs.SC) Computational Complexity (cs.CC) Symbolic computation 01 natural sciences Projection (linear algebra) Computer Science - Computational Complexity Integer Linear form ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION 0101 mathematics Algebraic number Mathematics |
| Zdroj: | ISSAC |
| DOI: | 10.48550/arxiv.1604.08944 |
| Popis: | Given a zero-dimensional polynomial system consisting of n integer polynomials in n variables, we propose a certified and complete method to compute all complex solutions of the system as well as a corresponding separating linear form l with coefficients of small bit size. For computing l, we need to project the solutions into one dimension along O(n) distinct directions but no further algebraic manipulations. The solutions are then directly reconstructed from the considered projections. The first step is deterministic, whereas the second step uses randomization, thus being Las-Vegas. The theoretical analysis of our approach shows that the overall cost for the two problems considered above is dominated by the cost of carrying out the projections. We also give bounds on the bit complexity of our algorithms that are exclusively stated in terms of the number of variables, the total degree and the bitsize of the input polynomials. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|