Polynomial Root-Finding Algorithms and Branched Covers
Myong-Hi Kim, Scott Sutherland · 1994
Abstract. We construct a family of root-finding algorithms which combine knowledge of the branched covering structure of a polynomial with a path-lifting algorithm for finding individual roots. In particular, the family includes an algorithm that computes an ǫ-factorization of a polynomial of degree d which has an arithmetic complexity of O ( d(log d) 2 | log ǫ | + d 2 (log d) 2). At the present time, this complexity is the best known in terms of the degree. Key words. Newton’s method, approximate zeros, arithmetic complexity, path-lifting method, branched covering. AMS subject classifications. 68Q25; Secondary 58C10, 65H05, 30C15, 58F08 Introduction. The problem of devising optimal methods for numerically approximating the roots of a polynomial has been of interest for several centuries, and is far from solved. There are numerous recent works on root-finding algorithms and their cost, for example, the work of Jenkins and Traub [JT70], Renegar [Ren87], Schönhage [Sch82], and Shub and Smale [SS85, SS86, Sma85]. This list is far from complete; the