Volume 65, pp. 63-92, 2026.

Preconditioning without a preconditioner using randomized block Krylov subspace methods

Tyler Chen, Caroline Huber, Ethan Lin, and Hajar Zaid

Abstract

We describe a randomized variant of the block conjugate gradient method for solving a single positive definite linear system of equations. This method provably outperforms the preconditioned conjugate gradient method with a broad class of Nyström-based preconditioners, without ever explicitly constructing a preconditioner. In analyzing our algorithm, we derive theoretical guarantees for new variants of the Nyström-preconditioned conjugate gradient method, which may be of separate interest. We also describe how our approach yields fast algorithms for key data-science tasks such as computing the entire ridge regression regularization path and generating multiple independent samples from a high-dimensional Gaussian distribution.

Full Text (PDF) [1.4 MB], BibTeX , DOI: 10.1553/etna_vol65s63

Key words

preconditioning, randomized, conjugate gradient, block Krylov subspace methods

AMS subject classifications

65F08, 65F60, 65F50, 68Q25

Links to the cited ETNA articles

[29]	Vol. 60 (2024), pp. 381-404 Andreas Frommer, Gustavo Ramirez-Hidalgo, Marcel Schweitzer, and Manuel Tsolakis: Polynomial preconditioning for the action of the matrix square root and inverse square root
[37]	Vol. 39 (2012), pp. 156-185 Martin H. Gutknecht: Spectral deflation in Krylov solvers: a theory of coordinate space based methods