×

A restarted Lanczos approximation to functions of a symmetric matrix. (English) Zbl 1220.65052

The need for computing functions of large, sparse matrices arises in many fields of science and technology. The prevailing method for approximating the matrix-vector product \(f(A)b\), where \(A \in \mathbb R^{n \times n}\) is symmetric, for a scalar, analytic function is the Lanczos approximation which requires the construction and storage of the orthonormal basis to the Krylov subspace. The problem is overcome when solving linear systems using Krylov subspace methods by truncating the subspace at \(m\) and restarting the process.
In this paper the authors re-derive the “first” restart method of M. Eiermann and O. G. Ernst [SIAM J. Numer. Anal. 44, No. 6, 2481–2504 (2006; Zbl 1129.65019)] that was discarded by them due to its instability, and present a restarted variant of the Lanczos approximation to \(f(A)b\) that preserves the symmetry of the problem and only requires the evaluation of a function of an \(m\times m\) matrix at each restart. The novelty of the new variant is that the error is expressed as an explicit partial fraction expansion of the divided differences. The authors also propose a simple heuristic that identifies when to halt the iterations.

MSC:

65F30 Other matrix algorithms (MSC2010)
15A16 Matrix exponential and similar functions of matrices
65F50 Computational methods for sparse matrices

Citations:

Zbl 1129.65019

Software:

GMRFLib
PDFBibTeX XMLCite
Full Text: DOI