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

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.