Title | ||
---|---|---|
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 @x(m,n,k)=O(mn^3)+O(k^3n^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. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1016/j.cam.2010.02.029 | J. Computational Applied Mathematics |
Keywords | Field | DocType |
block toeplitz system,m block column,m block row,block circulant matrix,toeplitz block,block diagonal matrix,direct method,toeplitz solvers,toeplitz system,non-banded toeplitz block,fast toeplitz solver,circulant matrix,computational complexity | Discrete mathematics,Direct method,Inverse,Combinatorics,Matrix (mathematics),Toeplitz matrix,Circulant matrix,Block matrix,Mathematics,Levinson recursion,Computational complexity theory | Journal |
Volume | Issue | ISSN |
234 | 5 | 0377-0427 |
Citations | PageRank | References |
3 | 0.41 | 7 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Andrey Chesnokov | 1 | 7 | 1.20 |
Marc Van Barel | 2 | 294 | 45.82 |