Geometry of polynomials and root-finding via path-lifting. (5th January 2018)

• Record Type: Journal Article
• Authors: Kim, Myong-Hi; Martens, Marco; Sutherland, Scott
• Is Part Of: Nonlinearity. Volume 31:Number 2(2018:Feb.)
• Page Start: 414
• Page End: 457
• Publication Date: 2018-01-05
• Subjects: root-finding -- Newton's method -- Voronoi region -- approximate zeros -- branched cover -- homotopy method -- alpha theory; Primary 65H05 -- Secondary 30C15 -- 37F10 -- 52C20 -- 57M12 -- 68Q25; Nonlinear theories -- Periodicals; Mathematical analysis -- Periodicals; Mathematical analysis; Nonlinear theories; Periodicals; 515
• DOI: 10.1088/1361-6544/aa8ca8
• Languages: English
• ISSNs: 0951-7715

Abstract

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 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 ) / ρ ζ | (where ρ ζ is the radius of convergence of the branch of f − 1 taking 0 to a root ζ ) 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 / ρ ζ ) . The average of log ⁡ ( 1 / ρ ζ ) over all polynomials f with d roots in the unit disk is O ( 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 .