A SYSTOLIC ARRAY FOR THE LINEAR-TIME SOLUTION OF TOEPLITZ SYSTEMS OF EQUATIONS

R. P. BRENT AND F. T. LUK

Abstract

The solution of an (n + 1) × (n + 1) Toeplitz system of linear equations on a one-dimensional systolic architecture is studied. Our implementation of an algorithm of Bareiss is shown to require only O(n) time and O(n) storage, i.e. constant storage per systolic processor.

Comments

Only the Abstract is given here. The full paper appeared as [1] (there are some unfortunate printer’s errors such as omitting parentheses in displayed matrices; the corrections should be self-evident). For related work, see [2]. The numerical stability of the Bareiss and Levinson algorithms (in the symmetric positive-definite case) is considered in [3].

References

1. R. P. Brent and F. T. Luk, “A systolic array for the linear-time solution of Toeplitz systems of equations”, J. of VLSI and Computer Systems 1, 1 (1983), 1–23. CR 8405-0339. Also appeared as Report TR 82-526, Department of Computer Science, Cornell University, November 1982; and as Report TR-CS-83-02, Department of Computer Science, ANU, January 1983, 29 pp. rpb078.

2. R. P. Brent, H. T. Kung and F. T. Luk, “Some linear-time algorithms for systolic arrays” (invited paper), in Information Processing 83 (edited by R. E. A. Mason), North-Holland, Amsterdam, 1983, 865–876. Preliminary version appeared as rpb079.

3. A. W. Bojanczyk, R. P. Brent and F. R. de Hoog, “Stability analysis of fast Toeplitz linear system solvers”, Report CMA-MR17-91, CMA, ANU, August 1991, 23 pp. rpb126.

(Brent) Department of Computer Science, Australian National University, Canberra

(Luk) Department of Computer Science, Cornell University, Ithaca, New York

1991 Mathematics Subject Classification. Primary 65Y10; Secondary 47B35, 65Y05, 68Q22, 68Q25, 68Q35.

Key words and phrases. Systolic arrays, Toeplitz matrices, linear equations, Bareiss algorithm, VLSI. Supported in part by US Army Research Office Grant DAAG 29-79-0124 and in part by the Centre

for Mathematical Analysis and the Mathematical Sciences Research Centre at the Australian National University.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1983, Computer Science Press, Inc. Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent. rpb078a typeset using AMS-L^{A}TEX