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

Marvin Randig; Dierk Schleicher; Robin Stoll

doi:10.1016/j.cam.2023.115427

paper

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

arXiv:1703.05847 · doi:10.1016/j.cam.2023.115427

Abstract

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 ( $1 0^{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.

24 pages, 19 figures. Update in v2 incorporates progress on polynomials of even higher degrees (greater than 1 billion)