Systolic designs for Bernoulli's method

DOI10.1016/0167-8191(90)90045-BMaRDI QIDQ921868zbMATH OpenOpenAlexFDO

Authors Konstantinos G. Margaritis, D. J. Evans

Publication date 1990

Published in Parallel Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-8191(90)90045-b

zbMATH Keywords

Bernoulli's methoddominant roots of a polynomialfault-tolerancelinear systolic arrayOCCAMpolynomial root solversystolic ring

Mathematics Subject Classification ID

Real polynomials: location of zeros (26C10) Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Numerical computation of solutions to single equations (65H05) Numerical algorithms for specific classes of architectures (65Y10) Cellular automata (computational aspects) (68Q80)

Review text

This paper studies the systolic implementation of Bernoulli's method for obtaining dominant roots of a polynomial of degree n, and offers two systolic architectures. The first one is a linear systolic array of n inner product step processors with bidirectional data flow. It has a throughput rate of 1/2 and its processor utilization is 1/2. The second architecture is a systolic ring. The ring requires only half of the cells of the linear array and now the data flow is unidirectional. Each cell is active during every cycle. The throughput rate is 1/2 while the processor utilization becomes 1. An important feature of the proposed ring architecture is that it degrades gracefully as the number of defective cells increases. This systolic solution is quite suitable both for hardware (using WSI techniques) and soft systolic implementation. Many implementation details and the possibilities to use the proposed architectures for the obtaining of a polynomial solver are also presented. A simulation program in OCCAM is listed in the Appendix. We remark that three different systolic designs for Bernoulli's method were also presented by the reviewer [Publ. Inst. Math., Nouv. Ser. 44(58), 137-142 (1988; Zbl 0678.68052)].

Recommendations

• A systolic ring architecture for solving polynomial equations
• scientific article; zbMATH DE number 4112025
• Systolic designs for the root-squaring method
• Systolic designs for Aitken's root finding method
• Systolic architectures for polynomial and polynomial matrix manipulations

Cited in

(6)

• A systolic design for the Aitken extrapolation formula
• Systolic designs for Aitken's root finding method
• Systolic designs for the root-squaring method
• A systolic ring architecture for solving polynomial equations
• scientific article; zbMATH DE number 4112025 (Why is no real title available?)
• A design of time-optimum and register-number-minimum systolic convolvers

This page was built for publication: Systolic designs for Bernoulli's method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q921868)