On the convergence of a parallel algorithm for finding polynomial zeros

The problem of finding the zeros of a polynomial p(z) of degree n is considered. Some results related to a parallel algorithm given by Bini and Gemignani are improved. The algorithm is a reformulation of Householder's sequential algorithm ([7]) that is based on the computation of the polynomial remainder sequence generated by the Euclidean scheme. The approximation to the sought after zeros (or factors) can be carried out if, at the generic j-th step of the Euclidean scheme, the modulus of a certain quantity βj, that depends on the remainder of the division, is 'sufficiently small.' This condition is verified through the detection of a strong break-point for the zeros, that is, a value of j such that if zi, i = 1,..., n are the zeros of p(z), then |a(zj+1)÷a(zj)| < 1 - 1÷nk for a given k and for a given function a(z). In this paper we present sufficient conditions and necessary conditions for the existence of a strong break point.