Computing eigenvalues of semi-infinite quasi-Toeplitz matrices

Abstract

A quasi-Toeplitz (QT) matrix is a semi-infinite matrix of the form $A=T(a)+E$ where $T(a)$ is the Toeplitz matrix with entries $(T(a){)}_{i,j}=a_{j-i}$, for $a_{j-i}\in \mathbb{C}$, $i,j\ge 1$, while $E$ is a matrix representing a compact operator in ${\ell }^2$. The matrix $A$ is finitely representable if $a_k=0$ for $k<-m$ and for $k>n$, given $m,n>0$, and if $E$ has a finite number of nonzero entries. The problem of numerically computing eigenpairs of a finitely representable QT matrix is investigated, i.e., pairs $(\lambda ,\mathbf{v})$ such that $A\mathbf{v}=\lambda \mathbf{v}$, with $\lambda \in \mathbb{C}$, $\mathbf{v}=(v_j{)}_{j\in {\mathbb{Z}}^{+}}$, $\mathbf{v}\ne 0$, and ${\sum }_{j=1}^{\infty }|v_j{|}^2<\infty$. It is shown that the problem is reduced to a finite nonlinear eigenvalue problem of the kind $WU(\lambda )\beta =0$, where $W$ is a constant matrix and $U$ depends on $\lambda$ and can be given in terms of either a Vandermonde matrix or a companion matrix. Algorithms relying on Newton's method applied to the equation $\det WU(\lambda )=0$ are analyzed. Numerical experiments show the effectiveness of this approach. The algorithms have been included in the CQT-Toolbox [Numer. Algorithms 81 (2019), no. 2, 741--769].

References in corpus (6)

• Semi-Infinite Quasi-Toeplitz Matrices with Applications to QBD Stochastic Processes
• On the exponential of semi-infinite quasi-Toeplitz matrices
• On the infinite-dimensional QR algorithm
• Solving quadratic matrix equations arising in random walks in the quarter plane
• A computational framework for two-dimensional random walks with restarts
• Computing several eigenvalues of nonlinear eigenvalue problems by selection