A parallel algorithm for simple roots of polynomials

Abstract

A method for finding simple roots of arbitrary polynomials based on divided differences is discussed. Theoretical background is presented for the case of simple roots. Numerical results are presented which show the algorithm finds simple and (usually) multiple zeros to an accuracy limited by the accuracy of polynomial evaluation. The method is designed for an SIMD parallel computer. The algorithm is compared to two other frequently used polynomial root finders, the Jenkins-Traub algorithm and Laguerre’s method.