Short Recurrence Relations for (Extended) Krylov Subspaces

Both Krylov and extended Krylov subspaces are used for numerous purposes, such as solving linear systems of equations, iterative methods for finding eigenvalues, and computation of matrix functions. For numerical reasons, it is most convenient to represent these subspaces as the span of a set of orthonormal basis vectors. We focus on the computation of these basis vectors. In general, orthonormal bases for an (extended) Krylov subspace are computed by means of so-called recurrence relations, which express a recursive link between the orthonormal vectors. The smaller the number of terms in this recurrence relation, the less computational effort is needed to find an orthonormal basis for the considered subspace. The structure of the recurrence relation is reflected in that of the so-called recurrence matrix, which is the matrix representation of the investigated linear operator with respect to the orthonormal basis. There are two sources of structure that arise in the matrix representation of a linear operator with respect to an orthonormal basis. The first originates from the choice of subspace with respect to which the matrix representation is generated: a Krylov subspace imposes a Hessenberg structure on the matrix representation of the operator, while an extended Krylov subspace imposes a so-called extended Hessenberg structure on the matrix representation of the operator. The second is due to any structure inherent in the linear operator itself. For example, the matrix representation of an Hermitian operator with respect to an orthonormal basis of a Krylov subspace is tridiagonal. The recurrence matrix will be studied for several matrix classes along with the accompanying recurrence relations. For the classical Krylov case, specific attention is paid to the class of matrices whose adjoint is a low rank perturbation of a low degree rational function in the matrix. This class of matrices, which we will refer to as BML-matrices, gives rise to a low rank structure in the recurrence matrix. In our analysis, a connection between this low rank part and GMRES residual vectors will come about, engendering the design of a new economical Arnoldi iteration. For the extended Krylov case, specific attention is paid to the class of unitary and Hermitian matrices. For the class of Hermitian matrices, some known results in the literature are placed in a broader perspective, with which the structure of the recurrence matrix can be predicted elegantly and from which a corresponding algorithm can be derived. For the class of unitary matrices, coupled recurrence relations are derived which form the basis of an algorithm that returns a sparse factorization of the recurrence matrix.status: publishe