Parallel solution of certain Toeplitz least-squares problems (Q1072345)

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 \textit{L. Elden} [SIAM J. Sci. Statist. Comput. 5, 229-236 (1984; Zbl 0546.65013)], 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 may be decomposed and solved on a small systolic array.