Finding polynomial roots by dynamical systems -- a case study
From MaRDI portal
Publication:2211136
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.
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
Cites work
- A Fast Adaptive Multipole Algorithm for Particle Simulations
- A modified Newton method for polynomials
- A small probabilistic universal set of starting points for finding roots of complex polynomials by Newton's method
- How to find all roots of complex polynomials by Newton's method.
- Newton's method in practice: finding all roots of polynomials of degree one million efficiently
- Numerical computation of polynomial zeros by means of Aberth's method
- On the distribution of roots of polynomials
- On the number of iterations of Newton's method for complex polynomials
- On the parallel evaluation of a sparse polynomial at a point
- On the speed of convergence of Newton's method for complex polynomials
- Unified convergence analysis for Picard iteration in \(n\)-dimensional vector spaces
- Über die Nullstellenverteilung zufälliger Polynome
Cited in
(10)- A Classification of Postcritically Finite Newton Maps
- Analytical approach for simplifying dynamical systems of polynomial type.
- Dynamics of Newton-like root finding methods
- The Weierstrass–Durand–Kerner root finder is not generally convergent
- On the efficiency of Newton and Broyden numerical methods in the investigation of the regular polygon problem of (\(N + 1\)) bodies
- On the efficient global dynamics of Newton’s method for complex polynomials
- Chaotic Root-finding for a Small Class of Polynomials
- Diverging orbits for the Ehrlich-Aberth and the Weierstrass root finders
- Numerical computation of the roots of Mandelbrot polynomials: an experimental analysis
- 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 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)
