An adaptive subdivision method for root finding of univariate polynomials

Abstract The most common methods for root finding of polynomials are iterative. This type of methods shows some drawbacks, like the impossibility of parallelization, the unpredictable nature of the iterations, that prevents to search roots inside a pre-specified region of complex plane, and the moderated degree of the polynomials that they can handle. This work describes a recursive root finding method. It is based on the winding number of plane curves, that is related to the number of zeros of a polynomial in a plane region. By our previous work (Garcia Zapata and Diaz Martin, 2014) we find the winding number at reasonable computational cost, so we can approximate the roots by recursive subdivision of the search region. This subdivision approach is parallelizable, with a known bound of the computational cost, and the search can be restrained, in contrast to the iterative methods. We use error returns to identify and avoid singular curves, adapting the subdivision to the roots. This allows us to handle high degree polynomials without resorting to the expensive multiprecision arithmetics of other recursive methods. A significant contribution is that we formally prove its correctness.