Newton's method in practice: finding all roots of polynomials of degree one million efficiently

Abstract

We use Newton's method to find all roots of several polynomials in one complex variable of degree up to and exceeding one million and show that the method, applied to appropriately chosen starting points, can be turned into an algorithm that can be applied routinely to find all roots without deflation and with the inherent numerical stability of Newton's method. We specify an algorithm that provably terminates and finds all roots of any polynomial of arbitrary degree, provided all roots are distinct and exact computation is available. It is known that Newton's method is inherently stable, so computing errors do not accumulate; we provide an exact bound on how much numerical precision is sufficient.

arXiv comment33 pages, 21 figures

References in corpus (2)

• On the speed of convergence of Newton's method for complex polynomials
• Internal addresses in the Mandelbrot set and Galois groups of polynomials

Cited by in corpus (8)

• A robust solver for elliptic PDEs in 3D complex geometries
• Newton's method in practice II: The iterated refinement Newton method and near-optimal complexity for finding all roots of some polynomials of very large degrees
• A Combinatorial classification of postcritically fixed Newton maps
• Some connections of complex dynamics
• A characterization of postcritically minimal Newton maps of complex exponential functions
• The Robust Newton Method for Polynomials and its Polynomiography
• The Weierstrass root finder is not generally convergent
• The Lattice of Amoebas