## 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).

## Abstract

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(*n*^{2}) to O(*n*).
The sequential algorithm takes time O(*n*^{2}); 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.
## Comments

A similar device for saving storage was
given in [78].
Go to next publication

Return to Richard Brent's index page