Systolic designs for the root-squaring method

Abstract

In this paper some systolic designs are presented for the implementation of the Graeffe root-squaring method for polynomial root solving. From a semi-systolic array, “retiming” transformations are applied to yield a purely systolic array that performs the squaring of the coefficients of an equation. The systolic array is then simulated soft-systolically in an OCCAM program listed in the Appendix. The overall design of a systolic system for the solution of equations based on the Graeffe method is also discussed.

Keywords:

• Systolic systems
• root finding methods
• parallel computing

C.R. Categories:

• 5.15
• 5.22