Computing approximate extended Krylov subspaces without explicit inversion

Thomas Mach, Miroslav S. Praníc, Raf Vandebril

Research output: Contribution to journalArticle

6 Citations (Scopus)

Abstract

It is shown that extended Krylov subspaces-under some assumptions-can be computed approximately without any explicit inversion or system solves involved. Instead, the necessary computations are done in an implicit way using the information from an enlarged standard Krylov subspace. For both the classical and extended Krylov spaces, the matrices capturing the recurrence coefficients can be retrieved by projecting the original matrix on a particular orthogonal basis of the associated (extended) Krylov space. It is also well-known that for (extended) Krylov spaces of full dimension, i.e., equal to the matrix size, the matrix of recurrences can be obtained directly by executing similarity transformations on the original matrix. 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 obliged to frequently solve systems of equations. In this paper the iterative and the direct similarity approach are integrated, thereby avoiding system solves. At first, an orthogonal basis of a standard Krylov subspace of dimension mℓ + mr + p and the matrix of recurrences are constructed iteratively. After that, cleverly chosen unitary similarity transformations are executed to alter the matrix of recurrences, thereby also changing the orthogonal basis vectors spanning the large Krylov space. Finally, only the first mℓ + mr - 1 new basis vectors are retained resulting in an orthogonal basis approximately spanning the extended Krylov subspace Kmℓ,mr (A, v) = span-A-mr+1v, . . . ,A-1v, v,Av,A2v, . . . ,Amℓ-1v . Numerical experiments support the claim that this approximation is very good if the large Krylov subspace approximately contains span-A-mr+1v, . . . ,A-1v. This can culminate in significant dimensionality reduction and as such can also lead to time savings when approximating or solving, e.g., matrix functions or equations.

Original languageEnglish
Pages (from-to)414-435
Number of pages22
JournalElectronic Transactions on Numerical Analysis
Volume40
Publication statusPublished - 2013
Externally publishedYes

Keywords

  • Extended Krylov
  • Iterative methods
  • Krylov
  • Polynomial approximation
  • QR factorization
  • Ritz values
  • Rotations

ASJC Scopus subject areas

  • Analysis

Fingerprint Dive into the research topics of 'Computing approximate extended Krylov subspaces without explicit inversion'. Together they form a unique fingerprint.

  • Cite this