Volume 48, pp. 362-372, 2018.

Non-Toeplitz decay bounds for inverses of Hermitian positive definite tridiagonal matrices

Andreas Frommer, Claudia Schimmel, and Marcel Schweitzer

Abstract

It is well known that the entries of the inverse of a Hermitian positive definite, banded matrix exhibit a decay away from the main diagonal if the condition number of the matrix is not too large compared to the matrix size. There is a rich literature on bounds which predict and explain this decay behavior. However, all the widely known results on exponential decay lead to a Toeplitz matrix of bounds, i.e., they yield the same bound for all entries along a sub- or superdiagonal. In general, there is no reason to expect the inverse of $A$ to have a Toeplitz structure so that this is an obvious shortcoming of these decay bounds. We construct an example of a tridiagonal matrix for which the difference between these decay bounds and the actual decay is especially pronounced and then show how these bounds can be adapted to better reflect the actual decay by investigating certain (modified) submatrices of $A$. As a by-product, we also investigate how the distribution of all eigenvalues of $A$ rather than just the spectral interval influences the decay behavior. Here, our results hold for matrices with a general, not necessarily banded, sparsity structure.

Full Text (PDF) [3.4 MB], BibTeX

Key words

matrix inverse, tridiagonal matrix, off-diagonal decay, Sherman–Morrison formula, Toeplitz matrix

AMS subject classifications

15A16, 65F50, 65F60

Links to the cited ETNA articles

[5]	Vol. 28 (2007-2008), pp. 16-39 Michele Benzi and Nader Razouk: Decay bounds and $O$($n$) algorithms for approximating functions of sparse matrices

ETNA articles which cite this article

Vol. 55 (2022), pp. 438-454 Marcel Schweitzer: Decay bounds for Bernstein functions of Hermitian matrices with applications to the fractional graph Laplacian

< Back