Polynomial root-finding algorithms and branched covers

1991/03/13 by Kim, Myong-Hi, Sutherland, Scott
#Dynamical Systems (math.DS) #FOS: Mathematics #Numerical Analysis (math.NA)

paper · doi:10.48550/arxiv.math/9201280

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 ε-factorization of the polynomial which has an arithmetic complexity of \Orderd²(log d)² + d(log d)²|logε|. At the present time (1993), this complexity is the best known in terms of the degree.

Related

• Iterative polynomial-root-finding procedure with enhanced accuracy
• Accelerated Approximation of the Complex Roots and Factors of a Univariate Polynomial
• Accelerated Approximation of the Complex Roots of a Univariate Polynomial (Extended Abstract)
• Root Radii and Subdivision for Polynomial Root-Finding
• New practical advances in polynomial root clustering