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

Shub, Michael; Smale, Steve

J. Am. Math. Soc. 6, No. 2, 459-501 (1993).

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)

MSC:

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)

Keywords:

Bezout’s theorem; complexity; homotopy methods; systems of polynomial equations; Newton’s method; ill-posed problems; convergence