Newton's method in practice: finding all roots of polynomials of degree one million efficiently

DOI10.1016/j.tcs.2017.03.025zbMath1375.65068arXiv1508.02935OpenAlexW2279235603MaRDI QIDQ2357369

Dierk Schleicher, Robin Stoll

Publication date: 13 June 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

algorithmNewton's methodpolynomialsnumerical stabilitycomplex variableroot findinghigh degree

Mathematics Subject Classification ID

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)

Related Items (16)

ON THE DISTANCE TO A ROOT OF COMPLEX POLYNOMIALS UNDER NEWTON'S METHOD ⋮ A Classification of Postcritically Finite Newton Maps ⋮ The Weierstrass–Durand–Kerner root finder is not generally convergent ⋮ A subspace expanding technique for global zero finding of multi-degree-of-freedom nonlinear systems ⋮ 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 ⋮ Finding polynomial roots by dynamical systems -- a case study ⋮ Unnamed Item ⋮ Some Connections of Complex Dynamics ⋮ On the speed of convergence of Newton’s method for complex polynomials ⋮ A characterization of postcritically minimal Newton maps of complex exponential functions ⋮ A combinatorial classification of postcritically fixed Newton maps ⋮ Puzzles and the Fatou–Shishikura injection for rational Newton maps ⋮ Free (rational) derivation ⋮ Combinatorial properties of Newton maps ⋮ On the efficient global dynamics of Newton’s method for complex polynomials ⋮ Newton's method in practice: finding all roots of polynomials of degree one million efficiently

Uses Software

• Eigensolve

Cites Work

• Unnamed Item
• Unnamed Item
• 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.
• Solving secular and polynomial equations: a multiprecision algorithm
• Newton's method in practice: finding all roots of polynomials of degree one million efficiently
• Internal addresses of the Mandelbrot set and Galois groups of polynomials
• On location and approximation of clusters of zeros of analytic functions
• Ü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
• On the number of iterations of Newton's method for complex polynomials
• Komplexe Dynamik, die Mandelbrot-Menge und das Newton-Verfahren oder: Von nutzloser und nützlicher Mathematik
• On the efficiency of algorithms of analysis
• Introduction to Dynamical Systems
• A small probabilistic universal set of starting points for finding roots of complex polynomials by Newton’s method
• Combinatorial properties of Newton maps
• A Classification of Postcritically Finite Newton Maps
• A combinatorial classification of postcritically fixed Newton maps
• How to find all roots of complex polynomials by Newton's method.

This page was built for publication: Newton's method in practice: finding all roots of polynomials of degree one million efficiently