Volume 58, pp. 538-567, 2023.

Inexact rational Krylov subspace methods for approximating the action of functions of matrices

Shengjie Xu and Fei Xue

Abstract

This paper concerns the theory and development of inexact rational Krylov subspace methods for approximating the action of a function of a matrix $f(A)$ to a column vector $b$. At each step of the rational Krylov subspace methods, a shifted linear system of equations needs to be solved to enlarge the subspace. For large-scale problems, such a linear system is usually solved approximately by an iterative method. The main question is how to relax the accuracy of these linear solves without negatively affecting the convergence of the approximation of $f(A)b$. Our insight into this issue is obtained by exploring the residual bounds for the rational Krylov subspace approximations of $f(A)b$, based on the decaying behavior of the entries in the first column of certain matrices of $A$ restricted to the rational Krylov subspaces. The decay bounds for these entries for both analytic functions and Markov functions can be efficiently and accurately evaluated by appropriate quadrature rules. A heuristic based on these bounds is proposed to relax the tolerances of the linear solves arising in each step of the rational Krylov subspace methods. As the algorithm progresses toward convergence, the linear solves can be performed with increasingly lower accuracy and computational cost. Numerical experiments for large nonsymmetric matrices show the effectiveness of the tolerance relaxation strategy for the inexact linear solves of rational Krylov subspace methods.

Full Text (PDF) [805 KB], BibTeX

Key words

matrix functions, rational Krylov subspace, inexact Arnoldi algorithm, decay bounds

AMS subject classifications

65D15, 65F10, 65F50, 65F60

Links to the cited ETNA articles

[6]	Vol. 28 (2007-2008), pp. 16-39 Michele Benzi and Nader Razouk: Decay bounds and $O$($n$) algorithms for approximating functions of sparse matrices

< Back