A SCHUR-ALGORITHM AND LINEARLY CONNECTED PROCESSOR ARRAY FOR TOEPLITZ-PLUS-HANKEL MATRICES

In this paper, a Levinson-Durbin-type algorithm for solving Toeplitz-plus-Hankel (T + H) linear systems of equations that is due to Heinig, Jankowski, and Rost will be used to induce a Schur-type algorithm for such systems. The approach used is quite different from that employed by, for example, Lev-Ari and Kailath. These authors use a modified form of Jacobi transformation (Schur reduction). A Schur-type algorithm is defined herein as one which efficiently computes the LDU-decomposition of the matrix. On the other hand, Levinson-Durbin-type algorithms are defined as those algorithms which efficiently compute the UDL-decomposition of the inverse of a matrix. It is also shown in this paper that the Schur algorithm so obtained is amenable to efficient implementation on a linearly connected array of processors in a manner which generalizes the results of Kung and Hu for symmetric Toeplitz matrices. Specifically, if T + H is of order n then the Schur algorithm runs on O(n) processors in O(n) time.