Marcel Schweitzer

Emil Krieger, Marcel Schweitzer

Randomized Krylov subspace methods that employ the sketch-and-solve paradigm to substantially reduce orthogonalization cost have recently shown great promise in speeding up computations for many core linear algebra tasks (e.g., solving linear systems, eigenvalue problems and matrix equations, as well as approximating the action of matrix functions on vectors) whenever a nonsymmetric matrix is involved. An important application that requires approximating the action of matrix functions on vectors is the implementation of exponential integration schemes for ordinary differential equations. In this paper, we specifically analyze randomized Krylov methods from this point of view. In particular, we use the residual of the underlying differential equation to derive a new, reliable a posteriori error estimate that can be used to monitor convergence and decide when to stop the iteration. To do so, we first develop a very general framework for Krylov ODE residuals that unifies existing results, simplifies their derivation and allows extending the concept to a wide variety of methods beyond randomized Arnoldi (e.g., rational Krylov methods, Krylov methods using a non-standard inner product, ...). In addition, we discuss certain aspects regarding the efficient implementation of sketched Krylov methods. Numerical experiments on large-scale ODE models from real-world applications illustrate the use of the sketched residual norm as stopping criterion as well as the general competitiveness of sketched Krylov methods for ODEs in comparison to other Krylov-based methods.

Bernhard Beckermann, Daniel Kressner, Marcel Schweitzer

We consider the task of updating a matrix function $f(A)$ when the matrix $A\in{\mathbb C}^{n \times n}$ is subject to a low-rank modification. In other words, we aim at approximating $f(A+D)-f(A)$ for a matrix $D$ of rank $k \ll n$. The approach proposed in this paper attains efficiency by projecting onto tensorized Krylov subspaces produced by matrix-vector multiplications with $A$ and $A^*$. We prove the approximations obtained from $m$ steps of the proposed methods are exact if $f$ is a polynomial of degree at most $m$ and use this as a basis for proving a variety of convergence results, in particular for the matrix exponential and for Markov functions. We illustrate the performance of our method by considering various examples from network analysis, where our approach can be used to cheaply update centrality and communicability measures.