A direct method to solve block banded block Toeplitz systems with non-banded Toeplitz blocks

摘要

A fast solution algorithm is proposed for solving block banded block Toeplitz systems with non-banded Toeplitz blocks. The algorithm constructs the circulant transformation of a given Toeplitz system and then by means of the Sherman-Morrison-Woodbury formula transforms its inverse to an inverse of the original matrix. The block circulant matrix with Toeplitz blocks is converted to a block diagonal matrix with Toeplitz blocks, and the resulting Toeplitz systems are solved by means of a fast Toeplitz solver. The computational complexity in the case one uses fast Toeplitz solvers is equal to xi(m, n, k) = O(mn(3)) + O(k(3)n(3)) flops, there are rn block rows and m block columns in the matrix, n is the order of blocks, 2k + 1 is the bandwidth. The validity of the approach is illustrated by numerical experiments.