Newton’s method as an interesting dynamical system and as an unexpectedly efficient root finder

Seminar: 
Group Actions and Dynamics
Event time: 
Monday, March 26, 2018 - 4:15pm to 5:15pm
Speaker: 
Dierk Schleicher
Speaker affiliation: 
Jacobs U.
Event description: 

1. We discuss Newton’s method as a dynamical system: ifp is a polynomial, then the Newton map is a rational map that very naturally ``wants to be iterated”. Among all rational maps, Newton’s method has the best understood dynamics, and these dynamical systems can be classified (in the sense of a theory developed by Bill Thurston). As a byproduct, we offer an answer to a question of Steve Smale on existence of attracting cycles of higher period (joint work with Kostiantyn Drach, Russell Lodge and Yauhen Mikulich).2. We outline theory about the complexity of Newton’s method as a root finder: unlike various other known methods,Newton as a root finder has both good theory and good implementation results in practice (partly joint work with Magnus Aspenberg, Todor Bilarev, Bela Bollobas, and Malte Lackmann). 3. We present recent experiments on finding all roots of Newton’s method for a number of large polynomials, for degrees exceeding one billion, on standard laptops with surprising ease and in short time, with observed complexity O(d log2 d) (joint with Marvin Randig, Simon Schmitt and Robin Stoll).