The Newton Method as Efficient Root Finder of Polynomials
Final Report Abstract
The fundamental goal of this project was to investigate Newton’s method as a root finder for complex polynomials in one variable. It has a reputation as being very fast once good approximations to all roots are known, but being globally unpredictable due to the “chaotic” nature of the iteration of rational maps especially on their Julia sets. We have encouraging theoretical as well as experimental results. In the theoretical direction, we show that in the “expected case” (under random assumptions on the distribution on the roots), the number of Newton iterations required to find all roots of a degree d polynomial with accuracy ε > 0 is at most O(d^2 log^4d + d log | log ε|); note that our method requires at least O(d^2) iterations for fundamental reasons, so our theoretical bounds in the expected case are nearly best possible (within our approach). We also have good worst-case bounds of the complexity that work in all cases, in particular allowing for multiple or near-multiple roots. On the experimental side, we showed that for a collection of explicit polynomials of degrees d = 2^n , selected only so that they can be evaluated e ciently, all roots can be found for n up to 20 and sometimes 23 (i.e. degrees exceeding 8 million) — and all this on standard laptop computers. In some heuristic methods, this is possible within hours of computing time (as opposed to months for certain professional software, for polynomials from their own demonstration package). Newton’s method is thus beginning to be recognized as a method with strong merits for root finding especially for high degree polynomials: it complements existing methods that are very e cient in theory but not practically useable (such as Pan’s algorithm) and methods that are practically e cient but for which little theory exists (such as the Ehrlich-Aberth method employed in the MPSolve 3.0 software package). Finally, we also worked on Newton’s method from the dynamical systems point of view and developed a classification of all rational Newton maps that come from transcendental functions: these are the Newton maps of entire functions peq with polynomials p and q.
Publications
- Newton’s method in practice: finding all roots of polynomials of degree one million e ciently. Journal of Theoretical Computer Science, recommended for publication in upcoming special issue on symbolic-numeric computation
Dierk Schleicher and Robin Stoll
- A small probabilistic universal set of starting points for finding roots of complex polynomials by Newton’s method. Mathematics of Computation 82 (2013), 443–457
Béla Bollobás, Malte Lackmann and Dierk Schleicher
- On Postcritically Minimal Newton Maps , PhD Thesis, Jacobs Univ. (2015). DNB-Server. VIII, 79 S.
Khudoyor Mamayusupov
- On the speed of convergence of Newton’s method for complex polynomials. Mathematics of Computation (2015)
Todor Bilarev, Magnus Aspenberg and Dierk Schleicher
(See online at https://doi.org/10.1090/mcom/2985) - On the Efficient Global Dynamics of Newton’s Method for Complex Polynomials. 2016, 26 pages
