Fast computation of zeros of polynomial systems with bounded degree under finite-precision
From MaRDI portal
complex polynomial systemsfinite-precisionfixed precise algorithmround-off errorSmale's 17th problemvariable precise algorithm
Polynomials and rational functions of one complex variable (30C10) General theory of numerical methods in complex analysis (potential theory, etc.) (65E05) Roundoff error (65G50) Numerical computation of solutions to systems of equations (65H10) Complexity and performance of numerical algorithms (65Y20)
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
- A numerical algorithm for zero counting. I: Complexity and accuracy
- Certified numerical homotopy tracking
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
- 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
- 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?)
- On a problem posed by Steve Smale
- On Smale's 17th problem: a probabilistic positive solution
- Smale's 17th problem: average polynomial time to compute affine and projective solutions
- The complexity of partial derivatives
Cited in
(13)- Accurate simple zeros of polynomials in floating point arithmetic
- Fast algorithms for zero-dimensional polynomial systems using duality
- A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time
- A randomized homotopy for the Hermitian eigenpair problem
- Sorting-based localization and stable computation of zeros of a polynomial. II.
- 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
- scientific article; zbMATH DE number 1305086 (Why is no real title available?)
- A faster solution to Smale's 17th problem. I: Real binomial systems
- Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems
- On Smale's 17th problem: a probabilistic positive solution
- A numerical algorithm for zero counting. I: Complexity and accuracy
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)
