Polynomial Root-Finding Algorithms and Branched Covers

DOI10.1137/S0097539791201587MaRDI QIDQ4291566zbMATH OpenFDO

Authors Myong-Hi Kim, Scott Sutherland

Publication date 2 January 1995

Published in SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

arithmetic complexitybranched covering structureNewton's methodpath-lifting algorithmpolynomialroot-finding algorithms

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) Topological dynamics (37B99) Holomorphic maps on manifolds (58C10) Numerical computation of solutions to single equations (65H05) Complexity and performance of numerical algorithms (65Y20)

Abstract: We construct a family of root-finding algorithms which exploit the branched covering structure of a polynomial of degree $d$ with a path-lifting algorithm for finding individual roots. In particular, the family includes an algorithm that computes an $epsilon$-factorization of the polynomial which has an arithmetic complexity of $Order{d}^2(logd{)}^2+d(logd{)}^2|logepsilon|$. At the present time (1993), this complexity is the best known in terms of the degree.

Recommendations

• Polynomial root-finding and polynomiography
• scientific article; zbMATH DE number 38950
• Remark on Algorithms to Find Roots of Polynomials
• Univariate polynomials, nearly optimal algorithms for factorization and rootfinding
• On root finding algorithms for complex functions with branch cuts
• A combinatorial construction of high order algorithms for finding polynomial roots of known multiplicity
• scientific article; zbMATH DE number 880382
• Algorithms for Modular Counting of Roots of Multivariate Polynomials
• Algorithms for modular counting of roots of multivariate polynomials
• Algorithmic aspects of branched coverings

Cited in

(16)

• Inverse power and Durand-Kerner iterations for univariate polynomial root-finding
• Finding a cluster of zeros of univariate polynomials
• Optimal and nearly optimal algorithms for approximating polynomial zeros
• Non-product form equilibrium probabilities in a class of two-station closed reentrant queueing networks
• Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration.
• A note on the finite variance of the averaging function for polynomial system solving
• On root finding algorithms for complex functions with branch cuts
• scientific article; zbMATH DE number 5356112 (Why is no real title available?)
• Geometry of polynomials and root-finding via path-lifting
• New progress in real and complex polynomial root-finding
• Topological complexity of a root finding algorithm
• Quadrature by two expansions for evaluating Helmholtz layer potentials
• Globally convergent, iterative path-following for algebraic equations
• Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
• Finding cactus roots in polynomial time
• Groebner basis methods for multichannel sampling with unknown offsets

This page was built for publication: Polynomial Root-Finding Algorithms and Branched Covers

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