Submitted by math_admin on Fri, 02/21/2020 - 16:51
preprint-id:
preprint-title:
Polynomial Root-Finding Algorithms and Branched Covers
preprint-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 $ \mathcal{O} (d^2(log d)^2 + d(log d)^2|log \epsilon |)$. At the present time (1993), this complexity is the best known in terms of the degree.
preprint-year:
1991