Complexity of Bezout’s theorem. IV: Probability of success; extensions. (English) Zbl 0843.65035

Summary: We estimate the probability that a given number of projective Newton steps applied to a linear homotopy of a system of \(n\) homogeneous polynomial equations in \(n+ 1\) complex variables of fixed degrees will find all the roots of the system. We also extend the framework of our analysis to cover the classical implicit function theorem and revisit the condition number in this context. Further complexity theory is developed.


65H10 Numerical computation of solutions to systems of equations
30C15 Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral)
65E05 General theory of numerical methods in complex analysis (potential theory, etc.)
12Y05 Computational aspects of field theory and polynomials (MSC2010)
65H20 Global methods, including homotopy approaches to the numerical solution of nonlinear equations
65Y20 Complexity and performance of numerical algorithms


Zbl 0821.65035
Full Text: DOI Link