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

✍ Scribed by Andrey Chesnokov; Marc Van Barel

• Book ID: 104007073
• Publisher: Elsevier Science
• Year: 2010
• Tongue: English
• Weight: 258 KB
• Volume: 234
• Category: Article
• ISSN: 0377-0427
• DOI: 10.1016/j.cam.2010.02.029

✦ Synopsis

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(mn 3 ) + O(k 3 n 3 ) 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.