Complexity of Bezout’s theorem. I: Geometric aspects. (English) Zbl 0821.65035

The paper deals with the complexity of homotopy methods for solving systems of polynomial equations. For general homotopy equations of the form \(f_ t (\zeta) = 0\), \(t \in [0,1]\), whose zeros are denoted by \(\zeta_ t\), the number \(l\) of steps (with \(0 = t_ 0 < t_ 1 < \cdots < t_ l = 1)\), that are necessary such that an approximate of the zero in the previous step is an appropriate starting point for Newton’s method in the next step, is estimated in terms of the distance of the curve \((f_ t, \zeta_ t)\) to the variety of ill-posed problems, the length of the curve \((f_ t)\), the maximum degree of the polynomials \(f_ t\) and a numerically known constant. The proof is based on a Kantorovich- type local convergence theorem for analytic functions.
Reviewer: W.Zulehner (Linz)


65H10 Numerical computation of solutions to systems of equations
65H20 Global methods, including homotopy approaches to the numerical solution of nonlinear equations
12Y05 Computational aspects of field theory and polynomials (MSC2010)
26C10 Real polynomials: location of zeros
30C15 Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral)
Full Text: DOI