On the Complexity of Solving Zero-Dimensional Polynomial Systems via Projection

DOI10.1145/2930889.2930934MaRDI QIDQ2985822zbMATH OpenOpenAlexFDO

Authors Cornelius Brand, Michael Sagraloff

Publication date 10 May 2017

Published in Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.08944

zbMATH Keywords

bit complexitycertified algorithmspolynomial system solvingresultant computationseparating form

Mathematics Subject Classification ID

Solving polynomial systems; resultants (13P15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Abstract: 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.

Recommendations

• On the Complexity of Polynomial Zeros
• Sharper complexity bounds for zero-dimensional Gröbner bases and polynomial system solving
• On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials
• scientific article; zbMATH DE number 4212207
• Fast algorithms for zero-dimensional polynomial systems using duality
• A fully polynomial time projective method
• Zero decomposition algorithms for systems of polynomial equations
• The complexity and geometry of numerically solving polynomial systems
• Algebraic complexity of computing polynomial zeros
• On the complexity of solving a bivariate polynomial system

Cited in

(11)

• Fast algorithms for zero-dimensional polynomial systems using duality
• On the bit complexity of polynomial system solving
• An algebraic framework for computing the topology of offsets to rational curves
• scientific article; zbMATH DE number 5168256 (Why is no real title available?)
• On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials
• Strong \(\mu\)-bases for rational tensor product surfaces and extraneous factors associated to bad base points and anomalies at infinity
• On Isolating Roots in a Multiple Field Extension
• Counting solutions of a polynomial system locally and exactly
• On the Topology of the Intersection Curve of Two Real Parameterized Algebraic Surfaces
• On the complexity of Chow and Hurwitz forms
• Computing the non-properness set of real polynomial maps in the plane

This page was built for publication: On the Complexity of Solving Zero-Dimensional Polynomial Systems via Projection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2985822)