A highly parallel algorithm for root extraction

Author

Rice, Thomas A. ; Jamieson, Leah H.

Author_Institution

Sch. of Electr. Eng., Purdue Univ., W. Lafayette, IN, USA

Volume

38

Issue

3

fYear

1989

fDate

3/1/1989 12:00:00 AM

Firstpage

443

Lastpage

449

Abstract

A parallel algorithm for extracting the roots of a polynomial is presented. The algorithm is based on Graeffe´s method, which is rarely used in serial implementations, because it is slower than many common serial algorithms, but is particularly well suited to parallel implementation. Graeffe´s method is an iterative technique, and parallelism is used to reduce the execution time per iteration. A high degree of parallelism is possible, and only simple interprocessor communication is required. For a degree-n polynomial executed on an (n+1)-processor SIMD machine, each iteration in the parallel algorithm has arithmetic complexity of approximately 2n and a communications overhead n. In general, arithmetic speedup is on the order of p/2 for a p-processor implementation

Keywords

computational complexity; iterative methods; parallel algorithms; polynomials; SIMD machine; arithmetic complexity; highly parallel algorithm; interprocessor communication; iterative technique; root extraction; roots of a polynomial; Arithmetic; Digital filters; Digital signal processing; Equations; Iterative algorithms; Iterative methods; Parallel algorithms; Parallel processing; Polynomials; Signal processing algorithms;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/12.21130

Filename

21130