Abstract: dvi (4K), pdf (92K), ps (32K).
Paper: dvi (55K), pdf (279K), ps (144K).
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.
It is conjectured in  that S(n) = O(log n).
Go to next publication
Return to Richard Brent's index page