2016/06/13 by Marko Lindner, Lindner, Marko, Torge Schmidt +1 · 1 citation
Computer Science · Mathematics · #47B36 #65F15 #Approximation Theory and Sequence Spaces #FOS: Mathematics #Holomorphic and Operator Theory #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #Primary 65J10 #Secondary 47A10 #Spectral Theory (math.SP)
paper · pdf · doi:10.48550/arxiv.1606.03941
openalex publication_date 2016/06/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study spectra and pseudospectra of certain bounded linear operators on\n\ℓ2( mathbb Z). The operators are generally non-normal, and their matrix\nrepresentation has a characteristic off-diagonal decay. Based on a result of\nChandler-Wilde, Chonchaiya and Lindner for tridiagonal infinite matrices, we\ndemonstrate an efficient algorithm for the computation of upper and lower\nbounds on the pseudospectrum of operators that are merely norm limits of band\nmatrices -- the so-called band-dominated operators. After approximation by a\nband matrix and fixing a parameter n\∈ mathbb N, one looks at n\nconsecutive columns k+1,...,k+n , k\∈ mathbb Z, of the corresponding\nmatrix and computes the smallest singular value of that section via QR\nfactorization. We here propose a QR factorization by a sequence of Givens\nrotations in such a way that a large part of the computation can be reused for\nthe factorization of the next submatrix -- when k is replaced by k+1. The\ncomputational cost for the next factorization(s) is mathcal O(nd) as\nopposed to a naive implementation with mathcal O(nd2), where d is the\nbandwidth. So our algorithm pays off for large bands, which is attractive when\napproximating band-dominated operators with a full (i.e. not banded) matrix.\n