A LOOKAHEAD ALGORITHM FOR THE SOLUTION OF BLOCK TOEPLITZ-SYSTEMS

We give a weakly stable algorithm to solve a block Toeplitz system of linear equations. If the lookahead steps taken to compute the paramete rs of the inversion formula for the block Toeplitz matrix are small co mpared to the order n of the matrix, the algorithm requires O(n(2)) fl oating-point operations. The parameters of the inversion formula are i nterpreted and computed in a recursive way as solutions of certain int erpolation problems given the formal Laurent series based on the data of the block Toeplitz matrix. (C) 1997 Elsevier Science Inc.