Efficient polynomial root-refiners: A survey and new record efficiency estimates

A typical iterative polynomial root-finder begins with a relatively slow process of computing a crude but sufficiently close initial approximation to a root and then rapidly refines it. The policy of using the same iterative process at both stages of computing an initial approximation and refining it, however, is neither necessary nor most effective. The efficiency of an iteration at the former stage resists formal study and is usually decided empirically, whereas formal study of the efficiency at the latter stage of refinement is not hard and is the subject of the current paper. We define this local efficiency as log10qd=log10(q1/d) (qq is the convergence order, and dd is the number of function evaluations per iteration); it is inversely proportional to the number of flops involved. Assuming that about 2n2n flops are needed per evaluation of a polynomial of a degree nn at a single point, we extend the definition to cover the recent matrix methods for polynomial root-finding as well as some methods that combine nn approximations to all nn roots to refine them simultaneously. For the approximation of a single root of a polynomial of degree nn, the maximum local efficiency achieved so far is log102≈0.301…log102≈0.301…, but we show its growth to infinity for simultaneous approximation of all nn roots as nn grows to infinity.