## Institute for Mathematical Sciences

## Preprint ims91-5

** M. Kim & S. Sutherland**
* Polynomial Root-Finding Algorithms and Branched Covers.*

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(\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.

View ims91-5 (PDF format)