pith. sign in

arxiv: 2506.18408 · v2 · submitted 2025-06-23 · 🧮 math.NA · cs.NA

Stabilizing randomized GMRES through flexible GMRES

Stefan G\"uttel , John W. Pearson This is my paper

Pith reviewed 2026-05-19 08:17 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords flexible GMRESsketched GMRESrandomized GMRESiterative solverspreconditioningresidual boundsnumerical linear algebrastability
0
0 comments X

The pith

Flexible GMRES wraps sketched GMRES as a preconditioner to stabilize randomized linear solvers with non-increasing residuals.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows how to use flexible GMRES as an outer iteration around sketched GMRES to create a practical randomized solver. A new bound is derived that controls the outer residual using the inner preconditioner's residual. This setup produces non-increasing residual norms while needing little parameter tuning and remaining efficient. Readers interested in iterative methods for large linear systems would value a randomized approach that adds stability without complexity.

Core claim

By applying flexible GMRES with sketched GMRES serving as the flexible preconditioner, and leveraging a new bound relating the FGMRES residual to the preconditioner residual, the method yields a randomized solver that is robust in generating non-increasing residual norms and requires very little parameter tuning.

What carries the argument

The new residual bound for flexible GMRES expressed in terms of the preconditioner residual, which allows the outer iteration to inherit stability from the inner sketched GMRES.

If this is right

  • The solver maintains non-increasing residual norms throughout the iteration.
  • It operates efficiently for large problems with minimal tuning of parameters.
  • The approach combines the speed of randomization with the robustness of flexible outer iterations.
  • Convergence can be controlled by ensuring the preconditioner residual is sufficiently small.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This wrapping technique might apply to other sketched or randomized inner solvers to improve their stability.
  • Practical implementations could see reduced sensitivity to choices like sketch size or restart parameters.
  • Further work could test the method on ill-conditioned systems from real applications to verify the bound's tightness.

Load-bearing premise

The sketched GMRES iteration must provide a sufficiently accurate and stable preconditioner whose residual bound controls the outer flexible GMRES convergence.

What would settle it

Numerical experiments where the combined FGMRES with sketched GMRES preconditioner fails to produce non-increasing residual norms or requires extensive tuning would disprove the practical robustness claim.

Figures

Figures reproduced from arXiv: 2506.18408 by John W. Pearson, Stefan G\"uttel.

Figure 1
Figure 1. Figure 1: Pseudocode for the FGMRES and FFOM algorithms. 2 FGMRES and FFOM For ease of reference, let us state in [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of FGMRES and FFOM convergence on an artificial matrix of size n = 1, 000. The inner preconditioner Mj corresponds to performing 100 GMRES iterations. We also show the convergence of restarted GMRES(100) as a standalone solver. The dashed black line shows our upper bound (4) on the FGMRES residual. At each iteration j, this bound can be evaluated cheaply by using only the residual of the (j − … view at source ↗
Figure 3
Figure 3. Figure 3: Restarting with a variable preconditioner Mj . 6 [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Residual convergence of FGMRES-stabilized sGMRES for the vas stokes 1M problem. At each FGMRES iteration, the inner sGMRES solver is terminated when the sketched basis SABk exceeds 1015 in condition number. We also show the convergence of restarted sGMRES using the same condition number crite￾rion for restarting. The dashed black line shows our upper bound (4) on the FGMRES residual. 4.1.1 Convergence per … view at source ↗
Figure 5
Figure 5. Figure 5: Wall-clock time versus residual of FGMRES-stabilized sGMRES for the vas stokes 1M problem, compared to some other randomized methods. a power basis without any orthogonalization! In this case, the number of Krylov basis vectors varies only between 28 ≤ k ≤ 31 per sGMRES cycle. We are surprised that t = 0 is also the choice that leads to the best time-to￾solution performance, coming close to GMRES-SDR(100, … view at source ↗
Figure 6
Figure 6. Figure 6: Exploring different values of the Arnoldi truncation parameter t for the vas stokes 1M problem. The stabilizing effect of FGMRES can be clearly seen, with FGMRES-sGMRES converging irrespective of the choice of t. Surprisingly, t = 0 (no orthogonalization at all) is the best choice for this problem, bringing FGMRES￾sGMRES close in performance to GMRES-SDR. On the right of [PITH_FULL_IMAGE:figures/full_fig_… view at source ↗
Figure 7
Figure 7. Figure 7: Exploring different values of the Arnoldi truncation parameter t for the NACA12 problem, with (left) and without (right) ILU preconditioning. 0 200 400 600 800 1000 time in seconds 10-4 10-2 100 residual norm ML_Geer with ILU preconditioner FGMRES-sGMRES (t = 0) FGMRES-sGMRES (t = 1) FGMRES-sGMRES (t = 2) FGMRES-sGMRES (t = 3) 0 500 1000 time in seconds 100 101 102 residual norm ML_Geer without preconditio… view at source ↗
Figure 8
Figure 8. Figure 8: Exploring different values of the Arnoldi truncation parameter t for the ML Geer problem, with (left) and without (right) ILU preconditioning. 13 [PITH_FULL_IMAGE:figures/full_fig_p013_8.png] view at source ↗
read the original abstract

We explore the use of flexible GMRES as an outer wrapper for sketched GMRES. Building on a new bound for the residual of FGMRES in terms of the residual of the preconditioner, we derive a practical randomized solver that requires very little parameter tuning, while still being efficient and robust in the sense of generating non-increasing residual norms.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The manuscript proposes wrapping sketched GMRES inside flexible GMRES (FGMRES) to stabilize the randomized inner iteration. It derives a new bound on the outer FGMRES residual expressed in terms of the residual produced by the (randomized) preconditioner and uses this bound to obtain a practical solver that requires little parameter tuning while producing non-increasing outer residual norms.

Significance. If the new residual bound extends rigorously to the stochastic preconditioner case and the resulting solver indeed delivers deterministic monotonicity with minimal tuning, the work would offer a useful theoretical and practical contribution to randomized iterative methods for large-scale linear systems. The approach leverages existing FGMRES flexibility while addressing a known stability drawback of sketched GMRES.

major comments (1)
  1. [§3 and abstract] The derivation of the new FGMRES residual bound (abstract and §3) is stated for a general preconditioner action. Because the inner sketched GMRES redraws its sketching matrix independently at each outer step, the preconditioner residual is a random variable. The manuscript should clarify whether the bound holds pathwise, in expectation, or with high probability, and whether this is sufficient to guarantee the claimed deterministic non-increasing outer residual norms on every realization.
minor comments (1)
  1. [§2] Notation for the sketching matrix and its distribution should be introduced consistently in §2 before being used in the bound derivation.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback. We address the major comment below and have updated the manuscript to incorporate the requested clarification.

read point-by-point responses

  1. Referee: [§3 and abstract] The derivation of the new FGMRES residual bound (abstract and §3) is stated for a general preconditioner action. Because the inner sketched GMRES redraws its sketching matrix independently at each outer step, the preconditioner residual is a random variable. The manuscript should clarify whether the bound holds pathwise, in expectation, or with high probability, and whether this is sufficient to guarantee the claimed deterministic non-increasing outer residual norms on every realization.

    Authors: The derivation in Section 3 is performed for an arbitrary preconditioner action and therefore holds pathwise: it is a deterministic relation between the outer residual and the residual norm returned by the preconditioner on that specific call, with no probabilistic assumptions placed on the preconditioner. Because the outer FGMRES iteration is deterministic once the sequence of preconditioner actions is fixed, the non-increasing property of the outer residual norms holds on every realization. The randomness in the sketched inner solver affects only the quality of each preconditioner residual; the bound and the monotonicity apply conditionally on the realized actions. We have revised the abstract and Section 3 to state explicitly that the bound holds pathwise and that the claimed non-increasing outer residuals are guaranteed deterministically for each run. revision: yes

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The paper claims to build on a new bound relating the FGMRES residual to the preconditioner residual, then uses this to obtain a randomized solver with non-increasing residual norms and little tuning. No equations or steps in the provided abstract or description reduce by construction to fitted inputs, self-definitions, or self-citation chains. The central result is presented as an independent derivation that controls outer convergence via the new bound, making the analysis self-contained without load-bearing reductions to prior fitted quantities or author-specific uniqueness theorems.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review provides no explicit free parameters, axioms, or invented entities; the central claim rests on the existence and utility of the new residual bound whose details are not shown.

pith-pipeline@v0.9.0 · 5568 in / 1053 out tokens · 39215 ms · 2026-05-19T08:17:00.247719+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

  • IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
    ?
    unclear

    Relation between the paper passage and the cited Recognition theorem.

    Building on a new bound for the residual of FGMRES in terms of the residual of the preconditioner, we derive a practical randomized solver that requires very little parameter tuning, while still being efficient and robust in the sense of generating non-increasing residual norms.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Flexible GMRES converges in two phases

    math.NA 2026-04 unverdicted novelty 6.0

    Flexible GMRES exhibits two phases of convergence, with a sharp residual bound that is geometric for tight inner tolerances and more pronounced in two phases for looser tolerances, and the bound is shown to be unimpro...

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages · cited by 1 Pith paper

  1. [1]

    Avron, P

    H. Avron, P. Maymounkov, and S. Toledo. Blendenpik: Supercharging LAPACK’s least-squares solver. SIAM J. Sci. Comput. , 32(3):1217–1236, 2010

    work page 2010

  2. [2]

    Balabanov and L

    O. Balabanov and L. Grigori. Randomized Gram–Schmidt process with application to GMRES. SIAM J. Sci. Comput. , 44(3):A1450–A1474, 2022

    work page 2022

  3. [3]

    Bucci, D

    A. Bucci, D. Palitta, and L. Robol. Randomized sketched TT-GMRES for linear systems with tensor structure. arXiv preprint arXiv:2409.09471 , 2024

    work page arXiv 2024

  4. [4]

    Burke, S

    L. Burke, S. G¨ uttel, and K. M. Soodhalter. GMRES with randomized sketching and deflated restarting. SIAM J. Matrix Anal. Appl. , 46(1):702– 725, 2025

    work page 2025

  5. [5]

    T. A. Davis and Y. Hu. The University of Florida sparse matrix collection. ACM Trans. Math. Software, 38(1):Art. 1, 2011

    work page 2011

  6. [6]

    G¨ uttel and I

    S. G¨ uttel and I. Simunec. A sketch-and-select Arnoldi process. SIAM J. Sci. Comput., 46(4):A2774–A2797, 2024

    work page 2024

  7. [7]

    Y. Jang, L. Grigori, E. Martin, and C. Content. Randomized flexible GM- RES with deflated restarting. Numer. Alg., 98(1):431–465, 2025

    work page 2025

  8. [8]

    Martinsson and J

    P.-G. Martinsson and J. A. Tropp. Randomized numerical linear algebra: Foundations and algorithms. Acta Numer., 29:403–572, 2020

    work page 2020

  9. [9]

    R. B. Morgan. GMRES with deflated restarting. SIAM J. Sci. Comput. , 24(1):20–37, 2002

    work page 2002

  10. [10]

    and Erichson, N

    R. Murray, J. Demmel, M. W. Mahoney, N. B. Erichson, M. Melnichenko, O. A. Malik, L. Grigori, P. Luszczek, M. Derezi´ nski, M. E. Lopes, T. Liang, H. Luo, and J. Dongarra. Randomized numerical linear algebra: A perspec- tive on the field with an eye to software. arXiv preprint arXiv:2302.11474, 2023

    work page arXiv 2023

  11. [11]

    Nakatsukasa and J

    Y. Nakatsukasa and J. A. Tropp. Fast and accurate randomized algorithms for linear systems and eigenvalue problems. SIAM J. Matrix Anal. Appl. , 45(2):1183–1214, 2024. 15

    work page 2024

  12. [12]

    M. L. Parks, E. de Sturler, G. Mackey, D. D. Johnson, and S. Maiti. Re- cycling Krylov subspaces for sequences of linear systems. SIAM J. Sci. Comput., 28(5):1651–1674, 2006

    work page 2006

  13. [13]

    Rokhlin and M

    V. Rokhlin and M. Tygert. A fast randomized algorithm for overdetermined linear least-squares regression. Proc. Natl. Acad. Sci. USA, 105(36):13212– 13217, 2008

    work page 2008

  14. [14]

    Y. Saad. A flexible inner-outer preconditioned GMRES algorithm. SIAM J. Sci. Comput. , 14(2):461–469, 1993

    work page 1993

  15. [15]

    Y. Saad. Iterative Methods for Sparse Linear Systems, 2nd edition . SIAM, Philadelphia, PA, 2003

    work page 2003

  16. [16]

    Saad and M

    Y. Saad and M. Schultz. GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Stat. Comput. , 7(3):856–869, 1986

    work page 1986

  17. [17]

    T. Sarlos. Improved approximation algorithms for large matrices via ran- dom projections. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pages 143–152. IEEE, 2006

    work page 2006

  18. [18]

    G. W. Stewart. A Krylov–Schur algorithm for large eigenproblems. SIAM J. Matrix Anal. Appl. , 23(3):601–614, 2002

    work page 2002

  19. [19]

    D. P. Woodruff. Sketching as a tool for numerical linear algebra. Found. Trends Theor. Comput. Sci. , 10(1–2):1–157, 2014

    work page 2014

  20. [20]

    Woolfe, E

    F. Woolfe, E. Liberty, V. Rokhlin, and M. Tygert. A fast randomized al- gorithm for the approximation of matrices. Appl. Comput. Harmon. Anal. , 25(3):335–366, 2008. 16

    work page 2008