Fast parallel algorithms for Graeffe's root squaring technique (Q1129507)

The authors propose two parallel implementations for an iteration step for the solution of an \(n\)-degree polynomial equation, where \(n\) can be very large. The algorithms are based on Graeffe's method for the calculation of the zeros of a polynomial. The parallel implementation of this method utilizes the special structure of the relevant matrix and is based on two different systolic architectures, built around mesh trees and multitrees. Estimates for the efficiency of the algorithms are also provided.