Speeding up Krylov subspace methods for computing f(A)b via randomization

Journal article

This work is concerned with the computation of the action of a matrix function f(A), such as the matrix exponential or the matrix square root, on a vector b. For a general matrix A, this can be done by computing the compression of A onto a suitable Krylov subspace. Such compression is usually computed by forming an orthonormal basis of the Krylov subspace using the Arnoldi method. In this work, we propose to compute (non-orthonormal) bases in a faster way and to use a fast randomized algorithm for least-squares problems to compute the compression of A onto the Krylov subspace. We present some numerical examples which show that our algorithms can be faster than the standard Arnoldi method while achieving comparable accuracy.

Authors: Cortinovis, A; Kressner, D; Nakatsukasa, YN

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Society for Industrial and Applied Mathematics
• Journal: SIAM Journal on Matrix Analysis and Applications
• Volume: 45
• Issue: 1
• Pages: 619 - 633
• Publication date: 2024-02-09
• Acceptance date: 2023-11-14
• DOI: 10.1137/22M1543458
• EISSN: 1095-7162
• ISSN: 0895-4798
• Language: English
• Keywords: nonorthonormal basis; sketching; randomized algorithms; matrix functions; least-squares problem; Krylov subspace method