A general framework for Krylov ODE residuals with applications to randomized Krylov methods

Randomized Krylov subspace methods that employ the sketch-and-solve paradigm to substantially reduce orthogonalization costs 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 (ODEs). 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 to 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 us to extend the concept to a wide variety of methods beyond the randomized Arnoldi scheme (e.g., rational Krylov methods, Krylov methods using a non-standard inner product, etc.). In addition, we discuss certain aspects regarding the efficient implementation of sketched Krylov methods. Numerical experiments for large-scale ODE models from real-world applications illustrate the use of the sketched residual norm as a stopping criterion as well as the general competitiveness of sketched Krylov methods for ODEs in comparison to other Krylov-based methods.