Geometry of polynomials and root-finding via path-lifting

DOI10.1088/1361-6544/aa8ca8zbMath1386.65139arXiv0903.3674OpenAlexW3104687137MaRDI QIDQ4606640

Myong-Hi Kim, Scott Sutherland, Marco Martens

Publication date: 8 March 2018

Published in: Nonlinearity (Search for Journal in Brave)

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

zbMATH Keywords

Newton's methodhomotopy methodbranched coverroot-findingVoronoi regionalpha theoryapproximate zeros

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical computation of solutions to systems of equations (65H10) Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Numerical computation of solutions to single equations (65H05) Dynamics of complex polynomials, rational maps, entire and meromorphic functions; Fatou and Julia sets (37F10)

Related Items

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, On the efficient global dynamics of Newton’s method for complex polynomials

Uses Software

• na20

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast linear homotopy to find approximate zeros of polynomial systems
• Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
• On dominating sequence method in the point estimate and Smale's theorem
• The continuous, desingularized Newton method for meromorphic functions
• Complexity of Bezout's theorem. VI: Geodesics in the condition (number) metric
• Complexity of Bezout's theorem. VII: Distance estimates in the condition metric
• On the worst-case arithmetic complexity of approximating zeros of polynomials
• Complexity of Bezout's theorem. V: Polynomial time
• Computing the Newtonian graph
• Estimations for the separation number of a polynomial system
• Implicit gamma theorems. I: Pseudoroots and pseudospectra
• Design, analysis, and implementation of a multiprecision polynomial rootfinder
• Simultaneous point estimates for Newton's method
• The theory of Smale's point estimation and its applications
• A note on the finite variance of the averaging function for polynomial system solving
• Complexity of Bezout's theorem. III: Condition number and packing
• On location and approximation of clusters of zeros of analytic functions
• On the Grunsky inequalities for univalent functions
• 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 Approximate Zeros and Rootfinding Algorithms for a Complex Polynomial
• On the efficiency of algorithms of analysis
• The Newtonian Graph of a Complex Polynomial
• The fundamental theorem of algebra and complexity theory
• Complexity of Bezout's Theorem I: Geometric Aspects
• On Algorithms for Solvingf(x)=0
• Polynomial Root-Finding Algorithms and Branched Covers
• Solving a Polynomial Equation: Some History and Recent Progress
• Convergence Criteria for Attracting Cycles of Newton's Method
• Iteration Methods for Finding all Zeros of a Polynomial Simultaneously
• Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
• Newton's method and the Computational Complexity of the Fundamental Theorem of Algebra
• How to be sure of finding a root of a complex polynomial using Newton's method
• The complexity and geometry of numerically solving polynomial systems.
• A modified Newton method for polynomials
• How to find all roots of complex polynomials by Newton's method.