Recycling givens rotations for the efficient approximation of pseudospectra of band-dominated operators
| Autor: | Torge Schmidt, Marko Lindner |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Primary 65J10
Secondary 47A10 47B36 65F15 Pseudospectrum Algebra and Number Theory Band matrix Tridiagonal matrix 010102 general mathematics Numerical Analysis (math.NA) 01 natural sciences QR decomposition Mathematics - Spectral Theory Combinatorics Section (fiber bundle) Matrix (mathematics) Singular value Factorization 0103 physical sciences FOS: Mathematics Mathematics - Numerical Analysis 010307 mathematical physics 0101 mathematics Spectral Theory (math.SP) Analysis Mathematics |
| Zdroj: | Operators and Matrices. :1171-1196 |
| ISSN: | 1846-3886 |
| DOI: | 10.7153/oam-2017-11-80 |
| Popis: | We study spectra and pseudospectra of certain bounded linear operators on $\ell^2({\mathbb Z})$. The operators are generally non-normal, and their matrix representation has a characteristic off-diagonal decay. Based on a result of Chandler-Wilde, Chonchaiya and Lindner for tridiagonal infinite matrices, we demonstrate an efficient algorithm for the computation of upper and lower bounds on the pseudospectrum of operators that are merely norm limits of band matrices -- the so-called band-dominated operators. After approximation by a band matrix and fixing a parameter $n\in{\mathbb N}$, one looks at $n$ consecutive columns $\{k+1,...,k+n\}$, $k\in{\mathbb Z}$, of the corresponding matrix and computes the smallest singular value of that section via QR factorization. We here propose a QR factorization by a sequence of Givens rotations in such a way that a large part of the computation can be reused for the factorization of the next submatrix -- when $k$ is replaced by $k+1$. The computational cost for the next factorization(s) is ${\mathcal O}(nd)$ as opposed to a naive implementation with ${\mathcal O}(nd^2)$, where $d$ is the bandwidth. So our algorithm pays off for large bands, which is attractive when approximating band-dominated operators with a full (i.e. not banded) matrix. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|