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