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

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 de...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2017-06, Vol.681, p.146-166
Main Authors: Schleicher, Dierk, Stoll, Robin
Format: Article
Language:English
Subjects:
Dynamical Systems
High degree
Mathematics
Newton's method
Polynomials
Root finding
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2017.03.025