Abstract
Newton’s method is well known as a root finder locally near the roots. It is often “not recommended” as a global root finder because of its “chaotic” properties. We give a very efficient theoretical upper bound on its speed of convergence: all roots of a degree d polynomial can be found with accuracy eps in O(d^2 log^4 d + d log\log eps) Newton iterations in the expected case — very close to the theoretical upper bound of O(d^2) for this method. In practice, all roots of polynomials of degree more than a million are found routinely and in (4log 2) d^2 iterations — in practice, this means less than a day for degree a million on standard laptops. A modified method, for which we do not yet have a complete theory, brings this down to 3 d log^2 d iterations, which in practice for certain polynomials finds all roots of degree a million in a matter of minutes.