Deterministic sketching for Krylov subspace methods
This work addresses runtime efficiency in numerical linear algebra for applications like matrix computations, but it is incremental as it builds on existing sketching techniques.
The paper tackled the problem of runtime savings in Krylov subspace methods by analyzing arbitrary sketching matrices, leading to a deterministic sketching approach using row subset selection that ensures subspace embeddings with probability 1. The proposed methods for matrix functions, linear systems, and eigenvalue problems showed similar performance to randomly sketched counterparts.
Randomized sketching is currently introduced into every area of numerical linear algebra. In Krylov subspace methods, it allows runtime savings at the cost of small accuracy reductions. This work offers a different view on sketching in Krylov methods by analyzing what subspace embeddings are obtained by arbitrary sketching matrices. The analysis gives rise to a deterministic sketching approach leveraging row subset selection techniques that yield subspace embeddings holding with probability 1. We propose deterministically sketched Krylov methods for matrix functions, linear systems, and eigenvalue problems that show a similar performance to their randomly sketched counterparts.