Randomized Krylov Subspace Methods for Shifted Linear Systems
Abstract
We propose several novel Krylov subspace algorithms termed shifted randomized GMRES (RandGMRES-Sh), shifted randomized FOM (RandFOM-Sh), shifted randomized GMRES with deflated restarting (RandGMRES-Sh-DR), and shifted randomized FOM with deflated restarting (RandFOM-Sh-DR), for solving shifted linear systems. These methods are designed to significantly reduce the computational overhead of orthogonal basis generation while preserving orthogonality under specific conditions. Besides, this unified framework makes it possible to solve all shifted linear systems at the same time by using a single shared basis. These new approaches combine multiple advanced techniques together effectively, such as randomized sketching, the control of collinear residual directions, and deflated restarting methods. Compared with the standard versions of traditional algorithms, the new algorithms show a steady but moderate improvement in convergence speed. Furthermore, we theoretically prove that although GMRES and sketched GMRES have different algorithmic solution steps, their iterates are all confined to and together span the same basic Krylov subspace. We also work out the theoretical relationship between the solutions produced by RandGMRES-Sh and RandFOM-Sh at the same iteration step before the first restart. Moreover, we strictly prove how the solutions of RandGMRES-Sh and RandFOM-Sh are related to those of their traditional versions, GMRES-Sh and FOM-Sh, respectively.
Related
- Factorized Krylov subspace methods for solving large Sylvester equations
- On the stability of basis construction in extended Krylov subspace methods
- On Convergence Behavior of Randomized Kaczmarz-type Methods for Solving Doubly Noisy Linear Systems
- Finite-Precision Symmetric Krylov Methods: Exact Rounding Examples, Block Paige Identities,and a Variable-Block Lanczos Model
- A note on the complexity of random subspace model-based methods for derivative-free optimization
BibTeX
@misc{yuan2026randomized,
title = {{Randomized Krylov Subspace Methods for Shifted Linear Systems}},
author = {Xiang Yuan and Gang Wu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.34964},
eprint = {2610.34964},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.34964},
}
RIS
TY - UNPB
TI - Randomized Krylov Subspace Methods for Shifted Linear Systems
AU - Xiang Yuan
AU - Gang Wu
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.34964
UR - https://arxiv.org/abs/2610.34964
AB - We propose several novel Krylov subspace algorithms termed shifted randomized GMRES (RandGMRES-Sh), shifted randomized FOM (RandFOM-Sh), shifted randomized GMRES with deflated restarting (RandGMRES-Sh-DR), and shifted randomized FOM with deflated restarting (RandFOM-Sh-DR), for solving shifted linear systems. These methods are designed to significantly reduce the computational overhead of orthogonal basis generation while preserving orthogonality under specific conditions. Besides, this unified framework makes it possible to solve all shifted linear systems at the same time by using a single shared basis. These new approaches combine multiple advanced techniques together effectively, such as randomized sketching, the control of collinear residual directions, and deflated restarting methods. Compared with the standard versions of traditional algorithms, the new algorithms show a steady but moderate improvement in convergence speed. Furthermore, we theoretically prove that although GMRES and sketched GMRES have different algorithmic solution steps, their iterates are all confined to and together span the same basic Krylov subspace. We also work out the theoretical relationship between the solutions produced by RandGMRES-Sh and RandFOM-Sh at the same iteration step before the first restart. Moreover, we strictly prove how the solutions of RandGMRES-Sh and RandFOM-Sh are related to those of their traditional versions, GMRES-Sh and FOM-Sh, respectively.
ER -