Title: Computing approximate extended Krylov subspaces without explicit inversion
Authors: Mach, Thomas * ×
Pranić, Miroslav *
Vandebril, Raf * #
Issue Date: 9-Dec-2013
Publisher: Kent State University
Series Title: Electronic Transactions on Numerical Analysis vol:40 pages:414-435
Abstract: It will be shown that extended Krylov subspaces --under some assumptions-- can
be computed approximately without any explicit inversion or
system solves involved. Instead we do the necessary computations 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,
avoiding thereby system solves. An orthogonal basis of a standard Krylov
subspace of dimension l+r+p and the matrix of recurrences are first
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 the first l+r-1 new basis vectors are retained
resulting in an orthogonal basis approximately spanning the extended Krylov

Numerical experiments support the claims that this approximation is very good
if the large Krylov subspace approximately contains the Krylov space constructed with the inverse matrix. This can culminate in nonneglectable dimensionality
reduction and as such can also lead to time savings when approximating or
solving, e.g., matrix functions or equations.
Description: Full article freely available at the homepage of Electronic Transactions on Numerical Analysis. See enclosed link.
ISSN: 1068-9613
Publication status: published
KU Leuven publication type: IT
Appears in Collections:NUMA, Numerical Analysis and Applied Mathematics Section
* (joint) first author
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
cover.pdf Published 124KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science