Fast computation of zeros of polynomial systems with bounded degree under finite-precision
From MaRDI portal
Smale's 17th problemround-off errorcomplex polynomial systemsfinite-precisionfixed precise algorithmvariable precise algorithm
General theory of numerical methods in complex analysis (potential theory, etc.) (65E05) Complexity and performance of numerical algorithms (65Y20) Roundoff error (65G50) Numerical computation of solutions to systems of equations (65H10) Polynomials and rational functions of one complex variable (30C10)
Abstract: A solution for Smale's 17th problem, for the case of systems with bounded degree was recently given. This solution, an algorithm computing approximate zeros of complex polynomial systems in average polynomial time, assumed infinite precision. In this paper we describe a finite-precision version of this algorithm. Our main result shows that this version works within the same time bounds and requires a precision which, on the average, amounts to a polynomial amount of bits in the mantissa of the intervening floating-point numbers.
Recommendations
- On Smale's 17th problem: a probabilistic positive solution
- A faster solution to Smale's 17th problem. I: Real binomial systems
- Smale's 17th problem: average polynomial time to compute affine and projective solutions
- Solving polynomial equations in smoothed polynomial time and a near solution to Smale's 17th problem
- A numerical algorithm for zero counting. I: Complexity and accuracy
Cites work
- scientific article; zbMATH DE number 421657 (Why is no real title available?)
- scientific article; zbMATH DE number 503395 (Why is no real title available?)
- scientific article; zbMATH DE number 1503621 (Why is no real title available?)
- scientific article; zbMATH DE number 846277 (Why is no real title available?)
- scientific article; zbMATH DE number 852536 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- A numerical algorithm for zero counting. I: Complexity and accuracy
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
- Certified numerical homotopy tracking
- Complexity estimates depending on condition and round-off error
- Complexity of Bezout's Theorem I: Geometric Aspects
- Complexity of Bezout's theorem. III: Condition number and packing
- Complexity of Bezout's theorem. V: Polynomial time
- Complexity of Bezout's theorem. VI: Geodesics in the condition (number) metric
- Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
- Fast linear homotopy to find approximate zeros of polynomial systems
- On Smale's 17th problem: a probabilistic positive solution
- On a problem posed by Steve Smale
- Smale's 17th problem: average polynomial time to compute affine and projective solutions
- The complexity of partial derivatives
Cited in
(12)- A faster solution to Smale's 17th problem. I: Real binomial systems
- A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time
- A numerical algorithm for zero counting. I: Complexity and accuracy
- On Smale's 17th problem: a probabilistic positive solution
- Accurate simple zeros of polynomials in floating point arithmetic
- Smale's 17th problem: average polynomial time to compute affine and projective solutions
- On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials
- Complexity of path-following methods for the eigenvalue problem
- Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems
- Fast algorithms for zero-dimensional polynomial systems using duality
- A randomized homotopy for the Hermitian eigenpair problem
- Sorting-based localization and stable computation of zeros of a polynomial. II.
This page was built for publication: Fast computation of zeros of polynomial systems with bounded degree under finite-precision
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5401702)
