A Schur algorithm and linearly connected processor array for Toeplitz-plus-Hankel matrices

Author

Zarowski, Christopher J.

Author_Institution

Dept. of Electr. Eng., Queen´´s Univ., Kingston, Ont., Canada

Volume

40

Issue

8

fYear

1992

fDate

8/1/1992 12:00:00 AM

Firstpage

2065

Lastpage

2078

Abstract

A Levinson-Durbin type algorithm for solving Toeplitz-plus-Hankel (T+H) linear systems of equations is used to induce a Schur-type algorithm for such systems. A Schur-type algorithm is defined 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 shown 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 S.-Y. Kung and Y.H. Ku (1983) 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

Keywords

matrix algebra; parallel algorithms; parallel architectures; LDU-decomposition; Levinson-Durbin algorithm; Schur algorithm; Toeplitz-plus-Hankel matrices; UDL-decomposition; linear equations; linearly connected processor array; matrix decomposition; parallel processor; symmetric Toeplitz matrices; Array signal processing; Equations; Geophysical signal processing; Jacobian matrices; Linear systems; Matrix converters; Matrix decomposition; Signal processing algorithms; Symmetric matrices; Transmission line matrix methods;

fLanguage

English

Journal_Title

Signal Processing, IEEE Transactions on

Publisher

ieee

ISSN

1053-587X

Type

jour

DOI

10.1109/78.150007

Filename

150007