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
to a column vector . 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 . Our insight into this issue is obtained by exploring the residual
bounds for the rational Krylov subspace approximations of , based on the
decaying behavior of the entries in the first column of certain matrices of
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
, DOI: 10.1553/etna_vol58s538
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
