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 an algorithm, based on Newton’s method, for finding all roots of univariate complex polynomials so that the observed complexity is linear in the degree, up to logarithmic factors. Unlike the usual Newton method, which finds at most one root at a time, it is global in the sense that it att...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computational and applied mathematics 2024-02, Vol.437, p.115427, Article 115427
Main Authors: Randig, Marvin, Schleicher, Dierk, Stoll, Robin
Format: Article
Language:English
Subjects:
Algorithm
Complexity
Iterated refinement
Mathematics
Newton's method
Polynomial
Root finding
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present an algorithm, based on Newton’s method, for finding all roots of univariate complex polynomials so that the observed complexity is linear in the degree, up to logarithmic factors. Unlike the usual Newton method, which finds at most one root at a time, it is global in the sense that it attempts to find all roots of polynomials simultaneously. We demonstrate the feasibility of this algorithm by employing it to find all roots of several families of polynomials of degrees up to more than one billion (109). In all cases, the observed (empirical) complexity for finding all roots of a polynomial of degree d – measured either as the number of Newton iterations or computing time – was between O(dlnd) and O(dln3d), with small constants.
ISSN:0377-0427
1879-1778
1879-1778
DOI:10.1016/j.cam.2023.115427