Geometry of polynomials and root-finding via path-lifting

DOI10.1088/1361-6544/AA8CA8MaRDI QIDQ4606640zbMATH OpenOpenAlexFDO

Authors Myong-Hi Kim, M. Martens, Scott Sutherland

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 methodroot-findinghomotopy methodbranched coverVoronoi 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) Dynamics of complex polynomials, rational maps, entire and meromorphic functions; Fatou and Julia sets (37F10) Numerical computation of solutions to single equations (65H05)

Abstract: Using the interplay between topological, combinatorial, and geometric properties of polynomials and analytic results (primarily the covering structure and distortion estimates), we analyze a path-lifting method for finding approximate zeros, similar to those studied by Smale, Shub, Kim, and others. Given any polynomial, this simple algorithm always converges to a root, except on a finite set of initial points lying on a circle of a given radius. Specifically, the algorithm we analyze consists of iterating ${\displaystyle }$z - frac{f(z)-t_kf(z_0)}{f'(z)}${\displaystyle }$ where the $t_k$ form a decreasing sequence of real numbers and $z_0$ is chosen on a circle containing all the roots. We show that the number of iterates required to locate an approximate zero of a polynomial $f$ depends only on $log|f(z_0)/h{o}_{z}eta|$ (where $h{o}_{z}eta$ is the radius of convergence of the branch of $f^{-1}$ taking $0$ to a root $zeta$) and the logarithm of the angle between $f(z_0)$ and certain critical values. Previous complexity results for related algorithms depend linearly on the reciprocals of these angles. Note that the complexity of the algorithm does not depend directly on the degree of $f$, but only on the geometry of the critical values. Furthermore, for any polynomial $f$ with distinct roots, the average number of steps required over all starting points taken on a circle containing all the roots is bounded by a constant times the average of $log(1/h{o}_{z}eta)$. The average of $log(1/h{o}_{z}eta)$ over all polynomials $f$ with $d$ roots in the unit disk is $mathcalO(d)$. This algorithm readily generalizes to finding all roots of a polynomial (without deflation); doing so increases the complexity by a factor of at most $d$.

Recommendations

• Polynomial Root-Finding Algorithms and Branched Covers
• Topological complexity of a root finding algorithm
• How to be sure of finding a root of a complex polynomial using Newton's method
• On the efficient global dynamics of Newton’s method for complex polynomials
• How to find all roots of complex polynomials by Newton's method.

Cites work

• scientific article; zbMATH DE number 421657 (Why is no real title available?)
• scientific article; zbMATH DE number 3811922 (Why is no real title available?)
• scientific article; zbMATH DE number 3628385 (Why is no real title available?)
• scientific article; zbMATH DE number 1016749 (Why is no real title available?)
• scientific article; zbMATH DE number 1069617 (Why is no real title available?)
• scientific article; zbMATH DE number 1096865 (Why is no real title available?)
• scientific article; zbMATH DE number 3992817 (Why is no real title available?)
• scientific article; zbMATH DE number 3260031 (Why is no real title available?)
• scientific article; zbMATH DE number 3383473 (Why is no real title available?)
• Computational Complexity: On the Geometry of Polynomials and a Theory of Cost: II
• A modified Newton method for polynomials
• A note on the finite variance of the averaging function for polynomial system solving
• Complexity of Bezout's Theorem I: Geometric Aspects
• Complexity of Bezout's theorem. III: Condition number and packing
• Complexity of Bezout's theorem. V: Polynomial time
• Complexity of Bezout's theorem. VI: Geodesics in the condition (number) metric
• Complexity of Bezout's theorem. VII: Distance estimates in the condition metric
• Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
• Computing the Newtonian graph
• Convergence Criteria for Attracting Cycles of Newton's Method
• Design, analysis, and implementation of a multiprecision polynomial rootfinder
• Estimations for the separation number of a polynomial system
• Fast linear homotopy to find approximate zeros of polynomial systems
• How to be sure of finding a root of a complex polynomial using Newton's method
• How to find all roots of complex polynomials by Newton's method.
• Implicit gamma theorems. I: Pseudoroots and pseudospectra
• Iteration Methods for Finding all Zeros of a Polynomial Simultaneously
• Newton's method and the computational complexity of the fundamental theorem of algebra
• Newton's method as a dynamical system: Efficient root finding of polynomials and the Riemann -function
• On Algorithms for Solvingf(x)=0
• On Approximate Zeros and Rootfinding Algorithms for a Complex Polynomial
• On dominating sequence method in the point estimate and Smale's theorem
• On location and approximation of clusters of zeros of analytic functions
• On the Grunsky inequalities for univalent functions
• On the efficiency of algorithms of analysis
• On the speed of convergence of Newton's method for complex polynomials
• On the worst-case arithmetic complexity of approximating zeros of polynomials
• Polynomial Root-Finding Algorithms and Branched Covers
• Simultaneous point estimates for Newton's method
• Solving a Polynomial Equation: Some History and Recent Progress
• The Newtonian Graph of a Complex Polynomial
• The complexity and geometry of numerically solving polynomial systems
• The continuous, desingularized Newton method for meromorphic functions
• The fundamental theorem of algebra and complexity theory
• The theory of Smale's point estimation and its applications
• Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding

Cited in

(7)

• Roots of polynomials and umbilics of surfaces
• Geometry of Truncated Symmetric Products and Real Roots of Real Polynomials
• On the paths to the zeros of a polynomial
• A convex geometric approach to counting the roots of a polynomial system
• 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
• scientific article; zbMATH DE number 6536324 (Why is no real title available?)

Describes a project that uses

Uses Software

• na20

This page was built for publication: Geometry of polynomials and root-finding via path-lifting

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