A systolic array for Toeplitz systems of equations

78. 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.

Abstract: dvi (3K), pdf (78K), ps (27K).

Paper: pdf (1459K).


The solution of an n × n 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.


The printers omitted parentheses in matrix expressions occurrring in equations (2.2), (3.7), (3.8), (4.4), (5.5), and also in examples 1-3. [Corrections have been made in the online version.]


For related work, see [79, 88, 177].

Go to next publication

Return to Richard Brent's index page