We survey some 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).