| Home > Publications > Reports > Numerical Analysis and Applied Mathematics (TW) |
TW 531
Andrey Chesnokov, Marc Van Barel
A direct method to solve block banded block Toeplitz systems with non-banded Toeplitz blocks
Abstract
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 a(m, n, k) = O(m n3)+O(k3 n3) flops, there are m 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.
report.pdf (511K) / mailto: M. Van Barel