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 ξ(m,n,k)=O(mn3)+O(k3n3)ξ(m,n,k)=O(mn3)+O(k3n3) flops, there are mm block rows and mm block columns in the matrix, nn is the order of blocks, 2k+12k+1 is the bandwidth. The validity of the approach is illustrated by numerical experiments.