Finding polynomial roots by dynamical systems -- a case study

DOI10.3934/DCDS.2020261zbMATH Open1456.37106arXiv2004.03217OpenAlexW3041937954MaRDI QIDQ2211136FDOQ2211136

Authors: Sergey Shemyakov, Roman Chernov, Dzmitry Rumiantsau, Dierk Schleicher, Simon Schmitt, Anton Shemyakov 

Publication date: 12 November 2020

Published in: Discrete and Continuous Dynamical Systems (Search for Journal in Brave)

Abstract: We investigate two well known dynamical systems that are designed to find roots of univariate polynomials by iteration: the methods known by Newton and by Ehrlich-Aberth. Both are known to have found all roots of high degree polynomials with good complexity. Our goal is to determine in which cases which of the two algorithms is more efficient. We come to the conclusion that Newton is faster when the polynomials are given by recursion so they can be evaluated in logarithmic time with respect to the degree, or when all the roots are all near the boundary of their convex hull. Conversely, Ehrlich-Aberth has the advantage when no fast evaluation of the polynomials is available, and when roots are in the interior of the convex hull of other roots.

Full work available at URL: https://arxiv.org/abs/2004.03217

Recommendations

• Diverging orbits for the Ehrlich-Aberth and the Weierstrass root finders
• 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
• How to find all roots of complex polynomials by Newton's method.
• On the efficient global dynamics of Newton’s method for complex polynomials
• Old and new nearly optimal polynomial root-finders

zbMATH Keywords

efficiencycomparisonNewton's methodpolynomialsexperimentsroot findingEhrlich-Aberth method

Mathematics Subject Classification ID

Dynamics of complex polynomials, rational maps, entire and meromorphic functions; Fatou and Julia sets (37F10) Numerical computation of roots of polynomial equations (65H04) Dynamical systems in numerical analysis (37N30)

Cites Work

• Numerical computation of polynomial zeros by means of Aberth's method
• A modified Newton method for polynomials
• A Fast Adaptive Multipole Algorithm for Particle Simulations
• Über die Nullstellenverteilung zufälliger Polynome
• How to find all roots of complex polynomials by Newton's method.
• On the distribution of roots of polynomials
• On the number of iterations of Newton's method for complex polynomials
• A small probabilistic universal set of starting points for finding roots of complex polynomials by Newton's method
• Unified convergence analysis for Picard iteration in \(n\)-dimensional vector spaces
• On the parallel evaluation of a sparse polynomial at a point
• Newton's method in practice: finding all roots of polynomials of degree one million efficiently
• On the speed of convergence of Newton's method for complex polynomials

Cited In (10)

• Numerical computation of the roots of Mandelbrot polynomials: an experimental analysis
• Dynamics of Newton-like root finding methods
• On the efficiency of Newton and Broyden numerical methods in the investigation of the regular polygon problem of (\(N + 1\)) bodies
• A Classification of Postcritically Finite Newton Maps
• Chaotic Root-finding for a Small Class of Polynomials
• On the efficient global dynamics of Newton’s method for complex polynomials
• 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
• The Weierstrass–Durand–Kerner root finder is not generally convergent
• Diverging orbits for the Ehrlich-Aberth and the Weierstrass root finders
• Analytical approach for simplifying dynamical systems of polynomial type.

Uses Software

• na10

This page was built for publication: Finding polynomial roots by dynamical systems -- a case study

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2211136)