Krylov Subspace Recycling For Matrix Functions

Abstract

The work in this thesis is concerned with the development of Krylov subspace recycling algorithms for the efficient evaluation of a sequence of matrix function applications on a set of vectors. Recycling methods are a special class of augmented Krylov subspace methods where the augmentation subspace for each problem is constructed or recycled from the Krylov subspace used to solve a previous problem in the sequence. If selected appropriately, the presence of the recycled subspace can aid in accelerating the convergence of the iterative solver, thereby reducing the overall computational cost and run time required to solve the full sequence of problems.

Our new algorithm, known as recycled Full Orthogonalization Method (rFOM) for functions of matrices, is shown to reduce the computational overhead and runtime required to evaluate a sequence of matrix function applications, when compared to the standard FOM approximation. In addition, we present theoretical results on the numerical stability and convergence or rFOM.

We introduce sketched-recycled FOM (srFOM), which incorporates randomized sketching into rFOM in order to avoid excessive orthogonalization costs when working with non-Hermitian matrices. We also present a stabilized version of srFOM which exploits an SVD based stabilization approach. We derive a-posteriori error estimates using the difference of two iterates, which can be evaluated cheaply without access to the full augmented Krylov basis.