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
DOI10.1016/j.cam.2023.115427zbMath1522.65075arXiv1703.05847OpenAlexW2606047152MaRDI QIDQ6073133
Dierk Schleicher, Robin Stoll, Marvin Randig
Publication date: 17 October 2023
Published in: Journal of Computational and Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1703.05847
Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) General theory of numerical methods in complex analysis (potential theory, etc.) (65E05) Numerical computation of roots of polynomial equations (65H04)
Cites Work
- Unnamed Item
- An iterated eigenvalue algorithm for approximating roots of univariate polynomials
- Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
- Numerical methods for roots of polynomials. Part I
- On the worst-case arithmetic complexity of approximating zeros of polynomials
- A 2002 update of the supplementary bibliography on roots of polynomials
- Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration.
- Finding polynomial roots by dynamical systems -- a case study
- Solving secular and polynomial equations: a multiprecision algorithm
- Newton's method in practice: finding all roots of polynomials of degree one million efficiently
- Über die Nullstellenverteilung zufälliger Polynome
- On the distribution of roots of polynomials
- On the speed of convergence of Newton’s method for complex polynomials
- Computational Complexity: On the Geometry of Polynomials and a Theory of Cost: II
- On the number of iterations of Newton's method for complex polynomials
- Geometry of polynomials and root-finding via path-lifting
- A small probabilistic universal set of starting points for finding roots of complex polynomials by Newton’s method
- Diverging orbits for the Ehrlich–Aberth and the Weierstrass root finders
- The Weierstrass–Durand–Kerner root finder is not generally convergent
- On the efficient global dynamics of Newton’s method for complex polynomials
- How to find all roots of complex polynomials by Newton's method.
This page was built for publication: 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