## Some linear-time algorithms for systolic arrays

79. R. P. Brent,
H. T. Kung
and
F. T. Luk,
Some linear-time algorithms for systolic arrays,
in * Information Processing 83* (edited by R.E.A. Mason),
North-Holland, Amsterdam, 1983, 865-876.
Retyped 2000.
arXiv:1004.3716v1
Abstract:
dvi (4K),
pdf (92K),
ps (32K).

Paper:
dvi (55K),
pdf (279K),
ps (144K).

## Abstract

We survey some recent results on linear-time algorithms for systolic arrays.
In particular, we show how the greatest common divisor (GCD) of two
polynomials of degree *n* over a finite field can be computed in time
O(*n*) on a linear systolic array of
O(*n*) cells; similarly for the GCD
of two *n*-bit binary numbers.
We show how *n* × *n* Toeplitz systems of
linear equations can be solved in time
O(*n*) on a linear array of O(*n*)
cells, each of which has constant memory size (independent of *n*).

Finally, we outline how a two-dimensional square array of
O(*n*) × O(*n*)
cells can be used to solve (to working accuracy) the eigenvalue problem for
a symmetric real *n* × *n* matrix in time
O(*nS*(*n*)). Here *S*(*n*) is a
slowly growing function of *n*; for practical purposes
*S*(*n*) can be
regarded as a constant.

In addition to their theoretical interest, these results have potential
applications in the areas of error-correcting codes, symbolic and algebraic
computations, signal processing and image processing. For example, systolic
GCD arrays for error correction have been implemented with the
micro-programmable "PSC" chip.

## Comments

For related work, see
[73,
74,
77,
78,
80,
82,
83,
84,
86,
96]
It is conjectured in [84]
that *S*(*n*) = O(log *n*).

Go to next publication

Return to Richard Brent's index page