Fast computation of zeros of polynomial systems with bounded degree under finite-precision

DOI10.1090/S0025-5718-2013-02765-2zbMATH Open1291.65158DBLPjournals/moc/BriquelCPR14arXiv1205.0869OpenAlexW2000736017WikidataQ57733092 ScholiaQ57733092MaRDI QIDQ5401702FDOQ5401702

Authors: Irenée Briquel, Felipe Cucker, Vera Roshchina, Javier Peña 

Publication date: 12 March 2014

Published in: Mathematics of Computation (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

Smale's 17th problemround-off errorcomplex polynomial systemsfinite-precisionfixed precise algorithmvariable precise algorithm

Mathematics Subject Classification ID

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• The complexity of partial derivatives
• Title not available (Why is that?)
• Smale's 17th problem: average polynomial time to compute affine and projective solutions
• Title not available (Why is that?)
• On a problem posed by Steve Smale
• On Smale's 17th problem: a probabilistic positive solution
• Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
• Complexity of Bezout's theorem. VI: Geodesics in the condition (number) metric
• Complexity of Bezout's theorem. V: Polynomial time
• Complexity of Bezout's theorem. III: Condition number and packing
• Complexity of Bezout's Theorem I: Geometric Aspects
• Title not available (Why is that?)
• Fast linear homotopy to find approximate zeros of polynomial systems
• Certified numerical homotopy tracking
• Complexity estimates depending on condition and round-off error
• A numerical algorithm for zero counting. I: Complexity and accuracy
• Title not available (Why is that?)

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.

Uses Software

• mctoolbox

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)