Parallel solution of certain Toeplitz least-squares problems

AbstractWe 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 may be decomposed and solved on a small systolic array