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.

On the convergence of a parallel algorithm for finding polynomial zeros

LUCCIO, Flaminia
1994-01-01

Abstract

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.
1994
Parallel and Distributed Processing
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10278/15758
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact