On a problem posed by Steve Smale
Peter Bürgisser, Felipe Cucker · Annals of Mathematics · 2011
The 17th of the problems proposed by Steve Smale for the 21st century asks for the existence of a deterministic algorithm computing an approximate solution of a system of n complex polynomials in n unknowns in time polynomial, on the average, in the size N of the input system.A partial solution to this problem was given by Carlos Beltrán and Luis Miguel Pardo who exhibited a randomized algorithm doing so.In this paper we further extend this result in several directions.Firstly, we exhibit a linear homotopy algorithm that efficiently implements a nonconstructive idea of Mike Shub.This algorithm is then used in a randomized algorithm, call it LV, à la Beltrán-Pardo.Secondly, we perform a smoothed analysis (in the sense of Spielman and Teng) of algorithm LV and prove that its smoothed complexity is polynomial in the input size and σ -1 , where σ controls the size of of the random perturbation of the input systems.Thirdly, we perform a condition-based analysis of LV.That is, we give a bound, for each system f , of the expected running time of LV with input f .In addition to its dependence on N this bound also depends on the condition of f .Fourthly, and to conclude, we return to Smale's 17th problem as originally formulated for deterministic algorithms.We exhibit such an algorithm and show that its average complexity is N O(log log N ) .This is nearly a solution to Smale's 17th problem.provide these definitions in full detail in Section 2. Before doing so, in the remainder of this section, we briefly describe the recent history of Smale's 17th problem and the particular contribution of the present paper.The following summary of notations should suffice for this purpose.We denote by H d the linear space of complex homogeneous polynomial systems in n + 1 variables, with a fixed degree pattern d = (d 1 , . . ., d n ).We let D = max i d i , N = dim C H d , and D = i d i .We endow this space with the unitarily invariant Bombieri-Weyl Hermitian product and consider the unit sphere S(H d ) with respect to the norm induced by this product.We then make this sphere a probability space by considering the uniform measure on it.The expression "on the average" refers to expectation on this probability space.Also, the expression "approximate zero" refers to a point for which Newton's method, starting at it, converges immediately, quadratically fast.This is the setting underlying the series of papers [22], [23], [24], [26], [25] -commonly referred to as "the Bézout series" -written by Shub and Smale during the first half of the 1990s, a collection of ideas, methods, and results that pervade all the research done in Smale's 17th problem since this was proposed.The overall idea in the Bézout series is to use a linear homotopy.That is, one starts with a system g and a zero ζ of g and considers the segment E f,g with extremities f and g.Here f is the system whose zero we want to compute.Almost surely, when one moves from g to f , the zero ζ of g follows a curve in projective space to end in a zero of f .The homotopy method consists of dividing the segment E f,g in a number, say k, of subsegments E i small enough to ensure that an approximate zero x i of the system at the origin of E i can be made into an approximate zero x i+1 of the system at its end (via one step of Newton's method).The difficulty of this overall idea lies in the following issues:(1) How does one choose the initial pair (g, ζ)? (2) How does one choose the subsegments E i ?In particular, how large should k be?The state of the art at the end of the Bézout series, i.e., in [25], showed an incomplete picture.For (2), the rule consisted of taking a regular subdivision of E f,g for a given k, executing the path-following procedure, and repeating with k replaced by 2k if the final point could not be shown to be an approximate zero of f .(Shub and Smale provided criteria for checking this.)Concerning (1), Shub and Smale proved that good initial pairs (g, ζ) (in the sense that the average number of iterations for the rule above was polynomial in the size of f ) existed for each degree pattern d, but they could not exhibit a procedure to generate one such pair.The next breakthrough took a decade to come.Beltrán and Pardo proposed in [4], [5] that the initial pair (g, ζ) should be randomly chosen.The consideration of randomized algorithms departs from the formulation of Smale's (