Computing approximate extended Krylov subspaces without explicit inversion

It will be shown that extended Krylov subspaces —under some assumptions— can be retrieved without any explicit inversion or system solves involved. Instead we do the necessary computations of A^{-1}v in an implicit way using the information from an enlarged standard Krylov subspace. It is well-known that both for classical and extended Krylov spaces, direct unitary similarity transformations exist providing us the matrix of recurrences. In practice, however, for large dimensions computing time is saved by making use of iterative procedures to gradually gather the recurrences in a matrix. Unfortunately, for extended Krylov spaces one is required to frequently solve, in some way or another a system of equations. In this article both techniques will be integrated. We start with an orthogonal basis of a standard Krylov subspace of dimension m+m'+p. Then we will apply a unitary similarity built by rotations compressing thereby significantly the initial subspace and resulting in an orthogonal basis approximately spanning the extended Krylov subspace K_{m,m'}(A,v) = span{A^{-m'+1}v, …, A^{-1}v, v, Av, A^2 v, …, A^{m-1}v}. Numerical experiments support our claims that this approximation is very good if the large Krylov subspace contains A^{-m'+1}v, …, A^{-1}v and thus can culminate in nonneglectable dimensionality reduction and as such also can lead to time savings when approximating, e.g., matrix functions.nrpages: 22status: publishe