A systolic array for the regularization of ill-conditioned least-squares problem with triangular Toeplitz matrix (Q1072346)

Ill-conditioned least-squares problems with triangular Toeplitz matrix are considered, and the regularization method of Tikhonov and Phillips is used to alleviate the ill-conditioning. An efficient algorithm for such problems has recently been given. The algorithm is based on orthogonal transformations and takes advantage of the Toeplitz structure. This paper describes the implementation of this algorithm in a systolic array. The array consists of 2n processor elements (for a problem with n unknowns), connected in a linear mesh, and it computes a decomposition of the matrix in 3n time steps. If data are pipelined, a new decomposition is output every 2n time steps.