Complexity of Bezout's theorem. VI: Geodesics in the condition (number) metric

DOI10.1007/s10208-007-9017-6zbMath1175.65060arXivmath/0702344OpenAlexW3101584966MaRDI QIDQ1022430

Michael Shub

Publication date: 22 June 2009

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

systems of polynomial equationscondition metriccomplexity measure

Mathematics Subject Classification ID

Numerical computation of solutions to systems of equations (65H10) Global methods, including homotopy approaches to the numerical solution of nonlinear equations (65H20) Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Complexity and performance of numerical algorithms (65Y20) Numerical computation of roots of polynomial equations (65H04)

Related Items

Certified Numerical Homotopy Tracking, Self-convexity and curvature, On the zeta Mahler measure function of the Jacobian determinant, condition numbers and the height of the generic discriminant, On the geometry and topology of the solution variety for polynomial system solving, A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time, Smale's fundamental theorem of algebra reconsidered, Complexity of path-following methods for the eigenvalue problem, A continuation method to solve polynomial systems and its complexity, Rigid continuation paths II. structured polynomial systems, Certified predictor-corrector tracking for Newton homotopies, Fast linear homotopy to find approximate zeros of polynomial systems, Spherical Radon transform and the average of the condition number on certain Schubert subvarieties of a Grassmannian, Geometry of polynomials and root-finding via path-lifting, Robust certified numerical homotopy tracking, The nearest complex polynomial with a zero in a given complex domain, A numerical algorithm for zero counting. III: Randomization and condition, Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric, On a problem posed by Steve Smale, Minimizing the discrete logarithmic energy on the sphere: The role of random polynomials, The unavoidable condition\dots A report on the book. Book review of: P. Bürgisser and F. Cucker, Condition. The geometry of numerical algorithms, Fast computation of zeros of polynomial systems with bounded degree under finite-precision, Condition length and complexity for the solution of polynomial systems, A note on the finite variance of the averaging function for polynomial system solving, Smale 17th Problem: Advances and Open Directions, Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems, Computing singular points of projective plane algebraic curves by homotopy continuation methods, A facility location formulation for stable polynomials and elliptic Fekete points, A randomized homotopy for the Hermitian eigenpair problem, A numerical realization of the conditions of Max Nöther's residual intersection theorem

Cites Work

• Unnamed Item
• Estimates on the distribution of the condition number of singular matrices
• On Smale's 17th problem: a probabilistic positive solution
• Complexity of Bezout's theorem. V: Polynomial time
• On the Riemannian geometry defined by self-concordant barriers and interior-point methods.
• Complexity of Bezout's theorem. III: Condition number and packing
• Complexity of Bezout's Theorem I: Geometric Aspects
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Complexity of Bezout’s Theorem IV: Probability of Success; Extensions