Premium
A note on the solution of not balanced banded Toeplitz systems
Author(s) -
Lotti G.
Publication year - 2007
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.548
Subject(s) - toeplitz matrix , mathematics , block (permutation group theory) , block matrix , rank (graph theory) , matrix (chemical analysis) , coefficient matrix , reduction (mathematics) , band matrix , diagonal , displacement (psychology) , algorithm , levinson recursion , combinatorics , pure mathematics , square matrix , symmetric matrix , geometry , psychology , eigenvalues and eigenvectors , physics , materials science , quantum mechanics , composite material , psychotherapist
Abstract A direct algorithm is presented for the solution of linear systems having banded Toeplitz coefficient matrix with unbalanced bandwidths. It is derived from the cyclic reduction algorithm, it makes use of techniques based on the displacement rank and it relies on the Morrison–Sherman–Woodbury formula. The algorithm always equals and sometimes outperforms the already known direct ones in terms of asymptotic computational cost. The case where the coefficient matrix is a block banded block Toeplitz matrix in block Hessenberg form is analyzed as well. The algorithm is numerically stable if applied to M ‐matrices that are point diagonally dominant by columns. Copyright © 2007 John Wiley & Sons, Ltd.