Sketch-and-Restart: Randomized Sketching in Quadrature-Based Restarting for Matrix Functions
Abstract
We develop a sketch-and-restart framework for computing the action of a matrix function on a vector, $f(A) b$, where A is large, sparse, and non-Hermitian. The framework combines quadrature-based restarting with Arnoldi-like decompositions generated by sketched or truncated Arnoldi processes. Within this framework, we develop two classes of restarted algorithms. The first uses a fixed Krylov subspace dimension and is based either on the sketched Arnoldi process or on a new sketched harmonic Arnoldi process proposed in this work. The second class chooses the Krylov subspace dimension adaptively by running the truncated Arnoldi process until the condition number of the generated basis, estimated from its sketch, exceeds a prescribed threshold. We also establish the convergence of the restarted sketched harmonic Arnoldi method for Stieltjes functions under the assumption that A is positive real. Numerical experiments demonstrate the effectiveness of the proposed framework, including the computational savings achieved through sketching, the storage reduction enabled by adaptive truncation, and the acceleration obtained from thick restarting.
Related
- On the Robustness of Sparse Randomized Sketching to FP16 Rounding on GPUs
- Constructive Tchakaloff results and well-conditioned quadrature through randomized least squares
- Optimal Averaged Gauss–Radau Quadrature for Functions with Endpoint Singularities
- Stable and effective restarting of the SS--RR and SS--RRR methods for computing partial eigenpairs of Hermitian matrices
- Generative modeling via hierarchical tensor sketching
BibTeX
@misc{guttel2026sketchandrestart,
title = {{Sketch-and-Restart: Randomized Sketching in Quadrature-Based Restarting for Matrix Functions}},
author = {Stefan Güttel and Jingyu Liu and Lauri Nyman},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2607.10354},
eprint = {2607.10354},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.10354},
}
RIS
TY - UNPB
TI - Sketch-and-Restart: Randomized Sketching in Quadrature-Based Restarting for Matrix Functions
AU - Stefan Güttel
AU - Jingyu Liu
AU - Lauri Nyman
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2607.10354
UR - https://arxiv.org/abs/2607.10354
AB - We develop a sketch-and-restart framework for computing the action of a matrix function on a vector, $f(A) b$, where A is large, sparse, and non-Hermitian. The framework combines quadrature-based restarting with Arnoldi-like decompositions generated by sketched or truncated Arnoldi processes. Within this framework, we develop two classes of restarted algorithms. The first uses a fixed Krylov subspace dimension and is based either on the sketched Arnoldi process or on a new sketched harmonic Arnoldi process proposed in this work. The second class chooses the Krylov subspace dimension adaptively by running the truncated Arnoldi process until the condition number of the generated basis, estimated from its sketch, exceeds a prescribed threshold. We also establish the convergence of the restarted sketched harmonic Arnoldi method for Stieltjes functions under the assumption that A is positive real. Numerical experiments demonstrate the effectiveness of the proposed framework, including the computational savings achieved through sketching, the storage reduction enabled by adaptive truncation, and the acceleration obtained from thick restarting.
ER -