Volume 47, pp. 100-126, 2017.

Block Krylov subspace methods for functions of matrices

Andreas Frommer, Kathryn Lund, and Daniel B. Szyld


A variety of block Krylov subspace methods have been successfully developed for linear systems and matrix equations. The application of block Krylov methods to compute matrix functions is, however, less established, despite the growing prevalence of matrix functions in scientific computing. Of particular importance is the evaluation of a matrix function on not just one but multiple vectors. The main contribution of this paper is a class of efficient block Krylov subspace methods tailored precisely to this task. With the full orthogonalization method (FOM) for linear systems forming the backbone of our theory, the resulting methods are referred to as B(FOM)2: block FOM for functions of matrices. Many other important results are obtained in the process of developing these new methods. Matrix-valued inner products are used to construct a general framework for block Krylov subspaces that encompasses already established results in the literature. Convergence bounds for B(FOM)2 are proven for Stieltjes functions applied to a class of matrices which are self-adjoint and positive definite with respect to the matrix-valued inner product. A detailed algorithm for B(FOM)2 with restarts is developed, whose efficiency is based on a recursive expression for the error, which is also used to update the solution. Numerical experiments demonstrate the power and versatility of this new class of methods for a variety of matrix-valued inner products, functions, and matrices.

Full Text (PDF) [745 KB], BibTeX

Key words

matrix functions, restarted Krylov subspace methods, block Krylov subspace methods, global methods

AMS subject classifications

65F60, 65F50, 65F10, 65F30

Links to the cited ETNA articles

[17]Vol. 12 (2001), pp. 216-233 A. A. Dubrulle: Retooling the method of block conjugate gradients
[22]Vol. 33 (2008-2009), pp. 207-220 L. Elbouyahyaoui, A. Messaoudi, and H. Sadok: Algebraic properties of the block GMRES and block Arnoldi methods

ETNA articles which cite this article

Vol. 51 (2019), pp. 240-261 Patrick Kürschner: Approximate residual-minimizing shift parameters for the low-rank ADI iteration
Vol. 58 (2023), pp. 115-135 Christian E. Schaerer, Daniel B. Szyld, and Pedro J. Torres: A posteriori superlinear convergence bounds for block conjugate gradient
Vol. 58 (2023), pp. 348-377 Alessandro Buccini, Lucas Onisk, and Lothar Reichel: Range restricted iterative methods for linear discrete ill-posed problems
Vol. 62 (2024), pp. 1-21 Kathryn Lund and Davide Palitta: Low-rank-modified Galerkin methods for the Lyapunov equation

< Back