EFFICIENT SOLUTION OF BLOCK LINEAR-SYSTEMS WITH TOEPLITZ ENTRIES USING A CHANNEL DECOMPOSITION TECHNIQUE

This paper is concerned with the development of efficient solvers for block linear systems with Toeplitz entries. Fast block Toeplitz solver s are required in a wide range of applications in the area of multicha nnel and multidimensional digital signal processing. The presentation and the derivation of all algorithms proposed in this paper are based on the context of multichannel FIR Wiener filtering. A novel channel d ecomposition technique is applied to obtain fast, order recursive algo rithms that require scalar operations, only. The proposed algorithms c an accommodate multichannel filters of different filter orders and man age to get free of matrix operations. Two basic algorithm structures a re derived, the Levinson type and the Schur type. They are both based on suitable permutations that unravel the recursive nature of the pert inent matrices and enable the development of fast block linear system solvers. Normalized versions are also derived and a simple test for de tecting the positive definiteness of a block matrix with Toeplitz entr ies, is obtained. An efficient lattice structure, that requires scalar operations, is also derived and is subsequently used to obtain Schur- type recursions. The Schur-type algorithm admits full parallelism and, if parallel processing environment is available, it reduces processin g time by an order of magnitude. To illustrate the structure of the pr oposed algorithms, Matlab code is provided for the fast Levinson-type algorithm, as well as for the Schur counterpart.