Parallel solution of Toeplitz least squares problems

88. A. W. Bojanczyk and R. P. Brent, Parallel solution of certain Toeplitz least squares problems, J. Linear Algebra and its Applications 77 (1986), 43-60. MR 88b:65160.

Paper: pdf (1078K).


We describe a systolic algorithm for solving a Toeplitz least-squares problem of special form. Such problems arise, for example, when Volterra convolution equations of the first kind are solved by regularization. The systolic algorithm is based on a sequential algorithm of Eldén, but we show how the storage requirements of Eldén's algorithm can be reduced from O(n2) to O(n). The sequential algorithm takes time O(n2); the systolic algorithm takes time O(n) using a linear systolic array of O(n) cells. We also show how large problems can be decomposed and solved on a small systolic array.


A similar device for saving storage was given in [78].

Go to next publication

Return to Richard Brent's index page