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
This work enables root-finding for extremely high-degree polynomials on ordinary hardware, addressing a scalability bottleneck for polynomial root-finding.
The authors developed a practical Newton-based method to find all roots of complex polynomials with degrees over one billion, achieving observed complexity between O(d ln d) and O(d ln^3 d) on standard desktop computers.
We present a practical implementation based on Newton's method to find all roots of several families of complex polynomials of degrees exceeding one billion ($10^9$) so that the observed complexity to find all roots is between $O(d\ln d)$ and $O(d\ln^3 d)$ (measuring complexity in terms of number of Newton iterations or computing time). All computations were performed successfully on standard desktop computers built between 2007 and 2012.