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(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.
Comments
A similar device for saving storage was
given in [78].
Go to next publication
Return to Richard Brent's index page