Multiple Recurrences and the Associated Matrix Structures Stemming From Normal Matrices
Clara Mertens, Raf Vandebril · SIAM Journal on Numerical Analysis · 2014
There are many classical results in which orthogonal vectors stemming from Krylov subspaces are linked to short recurrence relations, e.g., three term recurrences for Hermitian and short rational recurrences for unitary matrices. These recurrence coefficients can be captured in a Hessenberg matrix, whose structure reflects the relation between the spectrum of the original matrix and the recurrences. The easier the recurrences, the faster the orthogonal vectors can be computed possibly resulting in computational savings in the design of, e.g., iterative solvers. In this article we focus on multiple recurrence relations, i.e., the $(j+1)$st orthogonal vector satisfies $\mathbf{q}_{j+1} = \sum_{i=j-m}^j \rho_{j,i}A\mathbf{q}_i - \sum_{i=j-\ell}^j \gamma_{j,i}\mathbf{q}_i$ with $\rho_{j,i}$, $\gamma_{j,i}$ scalars and $A$ the matrix defining the Krylov space. Though many compelling results are around, the structure of the corresponding Hessenberg matrix is mostly deduced by analyzing the inner product relations. first review classical results on short multiple recurrences for normal matrices whose Hermitian conjugate can be written as a “low degree” rational function of the matrix. Instead of considering inner product relations, we reformulate this theory in a matrix setting. Moreover, the matrix building blocks allow us to also derive multiple recurrence relations for $B$-normal matrices, normal matrices whose eigenvalues lie on the union of curves in the complex plane, normal matrices perturbed by a low rank, and normal matrices $A$ satisfying a “low degree” relation $s(A^\ast)=p(A)q(A)^{-1}$. The theoretical results on the structure available in the Hessenberg matrix lead to a new way to compute the orthogonal vectors. The numerical experiments illustrate, however, that straightforward algorithms exploiting this structure are numerically very sensitive, and more research is required to develop robust algorithms.