Institute for Mathematical Sciences

Preprint ims09-01

Myong-Hi Kim, Marco Martens, and Scott Sutherland
A Universal Bound for the Average Cost of Root Finding

Abstract: We analyze a path-lifting algorithm for finding an approximate zero of acomplex polynomial, and show that for any polynomial with distinct roots in the unit disk, the average number of iterates this algorithm requires is universally bounded by a constant times the log of the condition number. In particular, this bound is independent of the degree $d$ of the polynomial. The average is taken over initial values $z$ with $|z| = 1 + 1/d$ using uniform measure.
View ims09-01 (PDF format)