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

DOI10.1090/S0025-5718-2013-02765-2zbMath1291.65158arXiv1205.0869WikidataQ57733092 ScholiaQ57733092MaRDI QIDQ5401702

Irenée Briquel, Vera Roshchina, Felipe Cucker, Javier F. Peña

Publication date: 12 March 2014

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

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

zbMATH Keywords

round-off error; Smale's 17th problem; complex polynomial systems; finite-precision; fixed precise algorithm; variable precise algorithm

Mathematics Subject Classification ID

65H10: Numerical computation of solutions to systems of equations

65G50: Roundoff error

65E05: General theory of numerical methods in complex analysis (potential theory, etc.)

65Y20: Complexity and performance of numerical algorithms

30C10: Polynomials and rational functions of one complex variable

Related Items

Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems, Complexity of path-following methods for the eigenvalue problem, A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time, A randomized homotopy for the Hermitian eigenpair problem

Uses Software

• mctoolbox

Cites Work

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