Pith. sign in

REVIEW 3 major objections 3 minor 38 references

Randomized biorthogonalization through a two-sided Gram-Schmidt process

T0 review · 3 major / 3 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Randomizing two-sided Gram-Schmidt by enforcing biorthogonality after sketching cuts the cost roughly in half and, in the paper's numerical experiments, yields better-conditioned bases.

desk verdict A solid, reviewable paper that extends randomized Gram-Schmidt to biorthogonalization; the conditioning story is partly heuristic because the anti-concentration bound is proved for fixed vectors, not the adaptive ones the algorithm actually builds. read the letter →

arxiv 2509.04386 v1 pith:MNMWOQZQ submitted 2025-09-04 math.NA cs.NA

Laura Grigori , Lorenzo Piccinini , Igor Simunec This is my paper · ORCID
classification math.NAcs.NA MSC 65F2565F15
keywords randomizedbiorthogonalizationtwo-sidedGram-Schmidtsketchedobliqueprojectorssubspaceembeddingsanti-concentrationconditionnumbernonsymmetricLanczos
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper proposes a randomized variant of the two-sided Gram-Schmidt process, the algorithm that takes two matrices X and Y and produces bases Q and P with the same column spaces and Q^T P = I. The variant replaces the exact biorthogonality condition with a much cheaper sketched condition: for a random sketching matrix that approximately preserves inner products, it asks that (Omega Q)^T (Omega P) = I. Because the sketched vectors are shorter, each orthogonalization step costs roughly half as much; because sketched inner products of two distinct unit vectors are, with high probability, not close to zero, the algorithm rarely encounters the near-breakdowns that make deterministic bases ill-conditioned. The paper proves this anti-concentration fact for Gaussian sketches, shows numerically it holds for sparse sign and other sketches, reports experiments where randomized bases have substantially smaller condition numbers, and demonstrates a nonsymmetric Lanczos variant with comparable eigenvalue residual convergence.

What carries the argument

The load-bearing object is the sketched oblique projector, which projects onto range(Q) while making the residual sketch-orthogonal to range(P); when the bases are sketch-biorthogonal it simplifies to Q (Omega P)^T Omega. Algorithm 3.1 subtracts this projector from each new column, mirroring deterministic two-sided Gram-Schmidt but with sketched inner products. The second mechanism is the anti-concentration estimate of Proposition 4.1, which shows that for Gaussian sketches two distinct unit vectors have sketched inner product near zero with probability O(s delta), so the normalization step d_i = <Omega q_i, Omega p_i> is unlikely to be tiny. This pair of ingredients converts a worst-case in

What would settle it

Take the paper's sparse sign sketch with zeta = min(s,8) and two fixed unit vectors x != y with <x,y> = 0; estimate P(|<Omega x, Omega y>| <= delta) over many draws for delta = 10^-2 and 10^-3 and compare with the Gaussian bound O(s delta). More decisively, run Algorithm 3.1 on matrices whose deterministic two-sided Gram-Schmidt produces near-breakdowns, such as the ill-conditioned example of Section 6.1.1, with many independent sparse sign sketches; if the condition numbers of Q and P grow at the same rate as deterministic CGS or MGS, or if tiny sketched inner products occur with probability

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that sketch-biorthogonality is a viable substitute for exact biorthogonality. Algorithm 3.1 computes Q and P with range(Q)=range(X), range(P)=range(Y), and (Omega Q)^T (Omega P)=I, where Omega is an epsilon-subspace embedding; when the sketch is cheap to apply, this halves the per-iteration arithmetic cost because inner products are evaluated in s dimensions instead of n. The sharper point is Proposition 4.1: for a Gaussian Omega and unit vectors x != y, the probability that |<Omega x, Omega y>| <= delta is at most 202 s delta. Thus two distinct sketched vectors are very unlikely to be almost orthogonal, even if x and y themselves are orthog

Load-bearing premise

The practical advantage in conditioning rests on the unlikelihood of near-orthogonal sketched vectors, which Proposition 4.1 proves only for Gaussian sketches; the sparse sign matrix recommended and used in the experiments is supported only numerically, so the paper's better-conditioned claim is a heuristic for the sketch actually deployed.

Editorial extensions

If this is right

  • With a sparse sign sketch costing O(zeta n) per application, each iteration of the randomized classical or modified Gram-Schmidt variant costs about 2 n i + 2 s i + zeta n instead of 4 n i, so about half the deterministic cost for the same n; the saved budget can buy a second pass with better stability.
  • Because |<Omega x, Omega y>| is unlikely to be below delta for Gaussian Omega, the normalization constants in Algorithm 3.1 are unlikely to be tiny, and consequently the condition numbers of the computed bases do not explode; the paper's ill-conditioned experiment shows cond(Q) falling from roughly 10^9 to 10^17 down to about 10^5 for the stabilized randomized variants.
  • The best practical variant is the randomized classical Gram-Schmidt with explicit oblique projection run twice, which matched the most accurate methods and was faster; a mixed-precision version of it is fastest but loses about nine orders of magnitude in the decomposition error on the ill-conditioned test.
  • In the nonsymmetric Lanczos setting, full randomized sketch-biorthogonalization of the Krylov bases removes the short-term recurrence, but since deterministic Lanczos needs full re-biorthogonalization anyway, the randomized method is competitive; its Hessenberg matrix satisfies a characteristic-polynomial optimality condition with respect to the sketched norm, and the experiments show residuals co

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper proves anti-concentration only for Gaussian sketches, yet the experiments use sparse sign matrices; if a proof for sparse sign, or a counterexample, were found, the practical claim about conditioning would be placed on the same footing as the algorithmic claim. This is the most direct testable extension.
  • Sketching may act as a regularizer rather than only a speed-up: the paper's Figure 4.1 indicates that even orthogonal vectors become non-orthogonal after sketching, so any basis pair headed for near-breakdown might be made safer by working in sketch coordinates.
  • In the randomized Lanczos method, the two Hessenberg matrices are no longer transposes and their eigenvalue sets can differ; the paper's experiments show comparable residual convergence for leading eigenvalues, leaving open how to reconcile or select between the two Ritz spectra when they disagree.
  • The characteristic-polynomial optimality result hints that the randomized method's convergence could be analyzed by minimal-residual polynomial arguments in the sketched norm, though the paper does not develop such a theory.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper proposes a randomized two-sided Gram-Schmidt process for biorthogonalizing two matrices X, Y in R^{n x m}. Instead of computing P^T Q = I, it constructs Q and P with range(Q)=range(X), range(P)=range(Y), and (ΩQ)^T ΩP = I for a sketching matrix Ω. Section 3 derives the algorithm from sketched oblique projectors and presents three implementations (rCGS, rMGS, rCGS_O). Section 4 gives Proposition 4.1, an anti-concentration bound for Gaussian sketches of fixed vectors, and uses it to argue that the randomized bases are unlikely to become ill-conditioned. Section 5 applies the process to the nonsymmetric Lanczos algorithm for eigenvalue/eigenvector approximation, including an optimality result for the characteristic polynomial of the sketched Hessenberg matrix. Section 6 reports experiments on ill- and well-conditioned inputs and on a nonsymmetric eigenvalue problem, showing lower cost, lower biorthogonality loss, and often smaller condition numbers than deterministic variants; mixed-precision implementations are considered in Appendix B.

Significance. If the claims hold, this is a useful and timely contribution: it extends randomized sketching from one-sided to two-sided Gram-Schmidt, gives a clean projector-based derivation, and demonstrates practical gains in the nonsymmetric Lanczos setting. The cost analysis and the exact-arithmetic sketch-biorthogonality construction are convincing, and the numerical study is broad and well organized. Credit is due for the careful comparison of several implementations and for the explicit algorithmic recipes. However, the theoretical explanation of improved conditioning is not yet rigorous as stated for the actual adaptive process, and there are two concrete algebraic/algorithmic issues, detailed below, that need correction before the paper is fully reliable.

major comments (3)
  1. [Section 4, discussion after Prop. 4.1] The inference from Proposition 4.1 to Algorithm 3.1 is not justified. Proposition 4.1 bounds the sketched inner product of a fixed pair of unit vectors, but in Algorithm 3.1 the vectors q_i and p_i are deterministic functions of the same Ω, and d_i = (Ωp_i)^T Ωq_i is effectively an adaptive pivot/determinant ratio of the sketch Gram matrix. A fixed-pair anti-concentration bound does not transfer automatically to such adaptive pairs. A rigorous statement would require anti-concentration for the pivot ratios or independent sketching at each step. In addition, Proposition 4.1 is for Gaussian Ω, whereas the sparse sign matrix recommended in Section 2.4.1 and used in the experiments is supported only numerically (Figure 4.1). The text's statement that 'it is extremely unlikely that Algorithm 3.1 constructs sketch-biorthogonal vectors with very large norms' is therefore stronger than what is p
  2. [Algorithms 2.1 and 3.1, lines 8-9] The normalization step is algebraically incorrect for negative d_i. The algorithms set q_i = q_i / sqrt(d_i) and p_i = p_i / (sqrt(d_i) * sign(d_i)). If d_i < 0, sqrt(d_i) is not real, and even interpreting the formula in complex arithmetic gives (Ωq_i)^T(Ωp_i) = sign(d_i) = -1, not +1 as required by the stated output condition. The paper only excludes d_i=0, not d_i<0. The standard fix is to use the absolute value, e.g. q_i = q_i / sqrt(|d_i|) and p_i = sign(d_i) p_i / sqrt(|d_i|). As written, the algorithm does not always produce (ΩQ)^T ΩP = I, so this is a load-bearing issue in the central construction.
  3. [Proposition 3.1(iv)] The formula for the sketched oblique projector is stated with the inverse in the wrong order: the text gives /C9_Ω = Q((ΩQ)^T ΩP)^{-1}(ΩP)^T Ω. The correct expression is Q((ΩP)^T ΩQ)^{-1}(ΩP)^T Ω. Indeed, the proof's verification that the residual is sketch-orthogonal to P uses the latter form, and the displayed equality (Q((ΩQ)^T ΩP)^{-1}(ΩP)^T Ω) Q = Q is false in general because ((ΩQ)^T ΩP)^{-1}(ΩP)^T ΩQ = A^{-1} A^T ≠ I. The later implementations in Section 3.2.3 use the correct inverse, so this appears to be a local but important error in the general proposition that should be corrected.
minor comments (3)
  1. [Throughout] Typographical issues: 'Lancozs' in the abstract; 'sketch-orthgonally' in Section 3.2; 'asympototic' in Appendix A. The notation in Algorithm 2.1, line 9, 'pi = pi/√di · sign(di)' is ambiguous; parenthesize the denominator or rewrite using abs/sign.
  2. [Section 6.2] For the nonsymmetric Lanczos experiments, the sketching parameters (sketch size s and sparsity ζ) are not stated. Since the theoretical support for the sparse sign sketch is only numerical, reporting these parameters would improve reproducibility.
  3. [Figure 4.1] The figure shows averaged and minimum sketched inner products over 100 trials. It would be useful to also report the maximum, since the anti-concentration concern is about the smallest values; however, the minimum already conveys the main point.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the randomized two-sided Gram-Schmidt construction is self-contained, the conditioning explanation rests on an independent probabilistic lemma, and no fitted parameter is renamed as a prediction.

full rationale

The paper's central derivation is Algorithm 3.1, which constructs Q and P by explicit normalization so that (ΩQ)^T ΩP = I. This is a construction, not a prediction: the sketch-biorthogonality is enforced by the definition of the scaling in lines 8–9, so claiming it as an output property is not circular. The improved-conditioning claim is supported by Proposition 4.1, an independent Gaussian anti-concentration bound proved from external results (the distribution of products of correlated Gaussians [25] and a Chernoff bound). Proposition 4.1 is applied in Section 4 to argue that the sketched inner products encountered by Algorithm 3.1 are unlikely to be very small; the paper's own text says the fixed-pair result makes it 'extremely unlikely' that the algorithm constructs near-sketch-orthogonal vectors. Strictly, the proposition is stated for fixed unit vectors while the algorithm's qi, pi depend on the same Ω, so the transfer is a heuristic gap rather than a proven theorem. This is a correctness/rigor concern, not circularity: the proposition is not defined in terms of the algorithm's output, and no equation reduces to its input by construction. The support for the sparse sign sketch (the actually deployed Ω) is explicitly numerical: Section 2.4.1 cites the oblivious subspace-embedding property, Section 4.1 reports that the anti-concentration phenomenon 'also holds numerically' for other sketches, and the text says 'we expect that results analogous to Proposition 4.1 could also be proved' — an admitted extrapolation, not a circular step. Proposition 5.1 is proved from the sketched oblique projector and Cayley-Hamilton, following the independent approach in Saad [33]; the author-overlapping citation [11] is used for an analogous proof pattern, not as the sole justification. Appendix B reports a mixed-precision accuracy loss as an empirical finding. No fitted parameter is renamed as a prediction: the only free parameter is the sketching sparsity ζ, which is taken from the literature, and the reported condition numbers come from numerical experiments rather than from fitting the analysis. Overall, the derivation chain is self-contained against external benchmarks; the weaknesses are heuristic extrapolation and a proof gap, not circularity.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper introduces no new physical or mathematical entities. It relies on standard assumptions of full rank, no breakdown, and subspace embedding properties. The only notable strain is that the theoretical anti-concentration guarantee is for Gaussian sketches, while the recommended practical sketch is sparse sign.

assumptions (5)
  • domain assumption The input matrices X, Y have full column rank with m < n.
    Stated in Section 2.3 before Algorithm 2.1; needed for the existence of biorthogonal bases.
  • domain assumption No breakdown: ⟨q_i, p_i⟩ ≠ 0 for all iterations i in the deterministic process (and ⟨Ωq_i, Ωp_i⟩ ≠ 0 for the randomized one).
    Remark 2.3 and Remark 3.2 explicitly assume breakdown never occurs; the analysis does not cover the breakdown case.
  • domain assumption The sketching matrix Ω is an oblivious ε-subspace embedding for range(X) and range(Y), with ε ∈ (0,1).
    Section 2.4 defines the property; Section 3.1 uses it to guarantee the sketched oblique projectors are well-defined and to justify the sketch-biorthogonality condition.
  • domain assumption The subspaces satisfy ΩQ ∩ (ΩP)⊥ = {0} so that the sketched oblique projector is unique.
    Assumed in Proposition 3.1(i); the proof shows this follows from the ε-embedding property for ε∈(0,1), so it is not an extra burden.
  • domain assumption Proposition 4.1 assumes a Gaussian sketch with i.i.d. rows; the numerical experiments use sparse sign, cosine, Hadamard.
    The theoretical anti-concentration result is proven only for Gaussian matrices (Section 4), while the recommended sketch in the algorithm is the sparse sign matrix (Section 2.4.1); the transfer is verified only numerically in Figure 4.1.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Randomized biorthogonalization through a two-sided Gram-Schmidt process." pith.science (2026). https://pith.science/paper/MNMWOQZQ

@misc{pith2026250904386,
  author       = {Pith},
  title        = {Pith review of: Randomized biorthogonalization through a two-sided Gram-Schmidt process},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MNMWOQZQ}},
  note         = {Machine review of arXiv:2509.04386}
}
abstract

We propose and analyze a randomized two-sided Gram-Schmidt process for the biorthogonalization of two given matrices $X, Y \in\mathbb{R}^{n\times m}$. The algorithm aims to find two matrices $Q, P \in\mathbb{R}^{n\times m}$ such that ${\rm range}(X) = {\rm range}(Q)$, ${\rm range}(Y) = {\rm range}(P)$ and $(\Omega Q)^T \Omega P = I$, where $\Omega \in\mathbb{R}^{s \times n}$ is a sketching matrix satisfying an oblivious subspace $\varepsilon$-embedding property; in other words, the biorthogonality condition on the columns of $Q$ and $P$ is replaced by an equivalent condition on their sketches. This randomized approach is computationally less expensive than the classical two-sided Gram-Schmidt process, has better numerical stability, and the condition number of the computed bases $Q, P$ is often smaller than in the deterministic case. Several different implementations of the randomized algorithm are analyzed and compared numerically. The randomized two-sided Gram-Schmidt process is applied to the nonsymmetric Lancozs algorithm for the approximation of eigenvalues and both left and right eigenvectors.

Figures

Figures reproduced from arXiv: 2509.04386 by the authors.

Figure 4.1
Figure 4.1. Sketched inner product hΩx, Ωyi of random orthogonal unit vectors x, y ∈ R n of dimension n = 104 , for different sketching sizes s = 25 : 25 : 103 and different sketching matrices Ω ∈ R s×n. Solid: average over 100 tests. Dash-dotted: minimum over 100 tests. product. However, Proposition 4.1 shows that, for a Gaussian sketching matrix Ω, the sketched inner product of any two normalized vectors q and p only has prob… view at source ↗
Figure 4
Figure 4. [PITH_FULL_IMAGE:figures/full_fig_p014_4.png] view at source ↗
Figure 6.1
Figure 6.1. Biorthogonality errors computed at each iteration, for ill c [PITH_FULL_IMAGE:figures/full_fig_p019_6_1.png] view at source ↗
Figures from the paper (5 more)
Figure 6
Figure 6. Figure 6 [PITH_FULL_IMAGE:figures/full_fig_p019_6.png]
Figure 6.2
Figure 6.2. Figure 6.2: Comparison of the condition numbers of Qi and Pi , the loss of (sketch-)biorthogonality and the angle between the (sketches of) qi and pi , for X and Y as in [PITH_FULL_IMAGE:figures/full_fig_p020_6_2.png]
Figure 6
Figure 6. Figure 6 [PITH_FULL_IMAGE:figures/full_fig_p020_6.png]
Figure 6.3
Figure 6.3. Figure 6.3: Comparison of the condition numbers of Qi and Pi , the loss of (sketch-)biorthogonality and the angle between the (sketches of) qi and pi , for X and Y as in [PITH_FULL_IMAGE:figures/full_fig_p022_6_3.png]
Figure 6.4
Figure 6.4. Figure 6.4: Convergence of the eigenvectors associated with the 10 la [PITH_FULL_IMAGE:figures/full_fig_p023_6_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

38 extracted references · 35 canonical work pages

  1. [1]

    Abramowitz and I

    M. Abramowitz and I. A. Stegun , Handbook of mathematical functions with formulas, graphs, and mathe- matical tables, vol. No. 55 of National Bureau of Standards Applied Mathema tics Series, U. S. Government Printing Office, W ashington, DC, 1964. For sale by the Superin tendent of Documents. pages 11, 26

    work page 1964

  2. [2]

    W. E. Arnoldi , The principle of minimized iterations in the solution of the matrix eigenvalue problem , Quar- terly of applied mathematics, 9 (1951), pp. 17–29. pages 14, 15

    work page 1951

  3. [3]

    J. K. Baksalary, O. M. Baksalary, and T. Szulc , A property of orthogonal projectors , Linear Algebra and its Applications, 354 (2002), pp. 35–39. pages 2

    work page 2002

  4. [4]

    Balabanov and L

    O. Balabanov and L. Grigori , Randomized Gram–Schmidt process with application to GMRES , SIAM Jour- nal on Scientific Computing, 44 (2022), pp. A1450–A1474. pag es 1, 6, 18, 26

    work page 2022

  5. [5]

    A553–A5 85

    , Randomized block Gram–Schmidt process for the solution of l inear systems and eigenvalue problems , SIAM Journal on Scientific Computing, 47 (2025), pp. A553–A5 85. pages 1

    work page 2025

  6. [6]

    Benzi, M

    M. Benzi, M. Rinelli, and I. Simunec , Estimation of spectral gaps for sparse symmetric matrices , arXiv preprint arXiv:2410.15349, (2024). pages 13

    arXiv 2024

  7. [7]

    Bj ¨orck, Solving linear least squares problems by Gram-Schmidt orth ogonalization, BIT Numerical Mathe- matics, 7 (1967), pp

    ˚ A. Bj ¨orck, Solving linear least squares problems by Gram-Schmidt orth ogonalization, BIT Numerical Mathe- matics, 7 (1967), pp. 1–21. pages 1

    work page 1967

  8. [8]

    Bj ¨orck and C

    ˚ A. Bj ¨orck and C. C. Paige , Loss and recapture of orthogonality in the modified Gram–Sch midt algorithm , SIAM Journal on Matrix Analysis and Applications, 13 (1992) , pp. 176–190. pages 1

    work page 1992

Show all 38 references
  1. [9]

    M. B. Cohen , Nearly tight oblivious subspace embeddings by trace inequa lities, in Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2 016, pp. 278–287. pages 7

    2016

  2. [10]

    J. K. Cullum and R. A. Willoughby , Lanczos algorithms for large symmetric eigenvalue computa tions. Vol. 23 1, vol. 41 of Classics in Applied Mathematics, Society for Ind ustrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002. Reprint of the 1985 original. pages 16

    2002

  3. [11]

    de Damas and L

    J.-G. de Damas and L. Grigori , Randomized implicitly restarted Arnoldi method for the non -symmetric eigenvalue problem , arXiv preprint arXiv:2407.03208, (2024). pages 1, 16

    2024 arXiv

  4. [12]

    , Randomized Krylov-Schur eigensolver with deflation , arXiv preprint arXiv:2508.05400, (2025). pages 1

    2025 arXiv

  5. [13]

    R. W. Freund, M. H. Gutknecht, and N. M. Nachtigal , An implementation of the look-ahead Lanczos algorithm for non-Hermitian matrices , SIAM Journal on Scientific Computing, 14 (1993), pp. 137–15 8. pages 1, 15

    1993

  6. [14]

    G. H. Golub and C. F. V an Loan , Matrix computations , JHU press, 2013. pages 1, 2

    2013

  7. [15]

    Grigori and E

    L. Grigori and E. Timsit , Randomized Householder QR , arXiv preprint arXiv:2405.10923, (2024). pages 1

    2024 arXiv

  8. [16]

    Grigori and Z

    L. Grigori and Z. Xue , Randomized strong rank-revealing QR for column subset sele ction and low-rank matrix approximation, arXiv preprint arXiv:2503.18496, (2025). pages 6

    2025 arXiv

  9. [17]

    G ¨uttel and M

    S. G ¨uttel and M. Schweitzer , Randomized sketching for Krylov approximations of large-s cale matrix func- tions, SIAM Journal on Matrix Analysis and Applications, 44 (2023 ), pp. 1073–1095. pages 1

    2023

  10. [18]

    N. J. Higham and T. Mary , Mixed precision algorithms in numerical linear algebra , Acta Numerica, 31 (2022), pp. 347–414. pages 26

    2022

  11. [19]

    I. M. Jaimoukha and E. M. Kasenally , Oblique production methods for large scale model reduction , SIAM Journal on Matrix Analysis and Applications, 16 (1995), pp. 602–627. pages 16

    1995

  12. [20]

    Kahan, B

    W. Kahan, B. N. Parlett, and E. Jiang , Residual bounds on approximate eigensystems of nonnormal matrices, SIAM Journal on Numerical Analysis, 19 (1982), pp. 470–484 . pages 17

    1982

  13. [21]

    Lanczos , An iteration method for the solution of the eigenvalue probl em of linear differential and integral operators, J

    C. Lanczos , An iteration method for the solution of the eigenvalue probl em of linear differential and integral operators, J. Res. Natl. Bur. Stand. B, 45 (1950), pp. 255–282. pages 1, 15

    1950

  14. [22]

    Martinsson and J

    P.-G. Martinsson and J. A. Tropp , Randomized numerical linear algebra: Foundations and algo rithms, Acta Numerica, 29 (2020), p. 403–572. pages 7

    2020

  15. [23]

    Meng and M

    X. Meng and M. W. Mahoney , Low-distortion subspace embeddings in input-sparsity tim e and applications to robust linear regression, in Proceedings of the forty-fifth annual ACM symposium on Th eory of computing, 2013, pp. 91–100. pages 7

    2013

  16. [24]

    R. B. Morgan and D. A. Nicely , Restarting the nonsymmetric Lanczos algorithm for eigenva lues and linear equations including multiple right-hand sides , SIAM Journal on Scientific Computing, 33 (2011), pp. 3037–

    2011

  17. [25]

    Nadarajah and T

    S. Nadarajah and T. K. Pog ´any, On the distribution of the product of correlated normal rand om variables , C. R. Math. Acad. Sci. Paris, 354 (2016), pp. 201–204. pages 1 1

    2016

  18. [26]

    Nakatsukasa and J

    Y. Nakatsukasa and J. A. Tropp , Fast and accurate randomized algorithms for linear systems and eigenvalue problems, SIAM Journal on Matrix Analysis and Applications, 45 (2024 ), pp. 1183–1214. pages 1, 6

    2024

  19. [27]

    Oktay and E

    E. Oktay and E. Carson , Using mixed precision in low-synchronization reorthogona lized block classical Gram- Schmidt, PAMM, 23 (2023), p. e202200060. pages 26

    2023

  20. [28]

    Palitta, M

    D. Palitta, M. Schweitzer, and V. Simoncini , Sketched and truncated polynomial Krylov methods: Evalu- ation of matrix functions , Numerical Linear Algebra with Applications, 32 (2025), p. e2596. pages 1

    2025

  21. [29]

    B. N. Parlett , Reduction to tridiagonal form and minimal realizations , SIAM Journal on Matrix Analysis and Applications, 13 (1992), pp. 567–593. pages 1, 15

    1992

  22. [30]

    B. N. Parlett and D. S. Scott , The Lanczos algorithm with selective orthogonalization , Math. Comp., 33 (1979), pp. 217–238. pages 16

    1979

  23. [31]

    B. N. Parlett, D. R. Taylor, and Z. A. Liu , A look-ahead Lanczos algorithm for unsymmetric matrices , Mathematics of computation, 44 (1985), pp. 105–124. pages 1 5

    1985

  24. [32]

    Saad , Krylov subspace methods on supercomputers , SIAM Journal on Scientific and Statistical Computing, 10 (1989), pp

    Y. Saad , Krylov subspace methods on supercomputers , SIAM Journal on Scientific and Statistical Computing, 10 (1989), pp. 1200–1232. pages 14

    1989

  25. [33]

    Saad , Numerical Methods for Large Eigenvalue Problems , Society for Industrial and Applied Mathematics,

    Y. Saad , Numerical Methods for Large Eigenvalue Problems , Society for Industrial and Applied Mathematics,

  26. [34]

    J. A. Tropp, A. Yurtsever, M. Udell, and V. Cevher , Streaming low-rank matrix approximation with an application to scientific simulation , SIAM Journal on Scientific Computing, 41 (2019), pp. A2430– A2463. pages 7

    2019

  27. [35]

    D. P. Woodruff et al. , Sketching as a tool for numerical linear algebra , Foundations and Trends ® in Theoretical Computer Science, 10 (2014), pp. 1–157. pages 6

    2014

  28. [36]

    Yamazaki, S

    I. Yamazaki, S. Tomov, and J. Dongarra , Mixed-precision Cholesky QR factorization and its case stu dies on multicore CPU with multiple GPUs , SIAM Journal on Scientific Computing, 37 (2015), pp. C307–C 330. pages 26

    2015

  29. [37]

    Yamazaki, S

    I. Yamazaki, S. Tomov, J. Kurzak, J. Dongarra, and J. Barlow , Mixed-precision block Gram Schmidt orthogonalization, in Proceedings of the 6th W orkshop on Latest Advances in Sca lable Algorithms for 24 Large-Scale Systems, 2015, pp. 1–8. pages 26

    2015

  30. [38]

    L. M. Yang, A. Fox, and G. Sanders , Rounding error analysis of mixed precision block Household er QR algorithms, SIAM Journal on Scientific Computing, 43 (2021), pp. A1723– A1753. pages 26 25 Appendix A. A technical lemma. The following technical lemma is needed in the proof o...

    2021

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.