Pith. sign in

REVIEW 4 major objections 5 minor 15 references

Anatomy of High-Performance Column-Pivoted QR Decomposition

T0 review · 4 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read This paper argues that a modular, sketch-driven QRCP framework can replace the standard LAPACK pivoted QR routine with up to 148x speedups while preserving pivot quality.

desk verdict A well-executed systems paper with real code and credible speedups; the empirical pivot-quality evidence is too thin to support the LAPACK-inclusion conclusion. read the letter →

arxiv 2507.00976 v1 pith:QK5ETVPW submitted 2025-07-01 cs.MS cs.NAmath.NA

Maksim Melnichenko , Riley Murray , William Killian , James Demmel , Michael W. Mahoney , Piotr Luszczek , Mark Gates This is my paper · ORCID
classification cs.MScs.NAmath.NA MSC 65F2568W2065Y05
keywords QRfactorizationcolumnpivotingrandomizednumericallinearalgebrablockedalgorithmsLU-basedQRCPGPUKahanmatrixLAPACKGEQP3
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

The paper introduces BQRRP, a blocked QR-with-column-pivoting (QRCP) framework that decides which columns to pivot from a single Gaussian sketch of the input, instead of the column-by-column norm updates that make the standard LAPACK routine GEQP3 memory-bound. It argues that this design closes most of the performance gap between pivoted and unpivoted QR on modern CPUs and works on GPUs too. On a dual AMD EPYC 9734 system the framework is reported to run up to 148x faster than GEQP3 and to reach 35-60% of unpivoted GEQRF speed; on an NVIDIA H100 the GPU version reaches about 60-65% of cuSOLVER's unpivoted QR. On the Kahan matrix, a hard input for pivoting, BQRRP's pivot quality is comparable to GEQP3's. If the results hold beyond the tested random full-rank matrices, the framework is a practical drop-in alternative to GEQP3.

What carries the argument

The central object is the sketched panel-pivoting loop. BQRRP forms a Gaussian sketch $M_{\mathrm{sk}} = S M$ with $S\in\mathbb{R}^{d\times m}$, $d=\lceil\gamma b\rceil$, before the main loop; at each block it runs a wide QRCP on the sketch, implemented in the recommended CPU version by a row-pivoted LU followed by an unpivoted QR rather than by GEQP3, to obtain a block of pivot columns. The pivoted panel is then factorized by a tall unpivoted QR, the trailing submatrix is updated by ORMQR, and the sketch is refreshed deterministically with the formula $R_{\mathrm{sk}}^{12} - R_{\mathrm{sk}}^{11}(R_{11})^{-1}R_{12}$. The framework is modular: the wide-QRCP, rank estimator, tall-QR, apply-Q, and permutation routines are user-selectable, and the GPU version replaces sequential column swaps with a parallel copy-based permutation.

What would settle it

Run BQRRP and GEQP3 on a Kahan-type matrix with a smaller angle parameter, or on a matrix with a narrow singular-value gap and nearly equal column norms, and compute the trailing residual-norm ratios $\|R_{\mathrm{geqp3}}(i:,i:)\|_F/\|R_{\mathrm{bqrrp}}(i:,i:)\|_F$; a systematic rise well above 1 at intermediate indices, or a rank estimate that diverges from the true rank, would show the sketch loses the pivot signal on structured inputs.

Watch

Extended reading notes

Core claim

BQRRP treats QRCP as a block algorithm whose pivot choices come from a cheap randomized sketch rather than from repeated full-matrix column-norm updates. The paper's central empirical claim is that, implemented with an LU-based wide QRCP, unpivoted tall QR, and ORMQR for the trailing update, BQRRP CPU reaches up to 148x the speed of LAPACK's GEQP3 on a dual AMD EPYC 9734 system and up to 19x on an Intel Xeon, while sustaining 35-60% of unpivoted GEQRF performance on CPUs and 60-65% of cuSOLVER's unpivoted QR on an H100 GPU. The paper also claims pivot quality comparable to GEQP3 on the Kahan matrix, with divergence mainly near sharp singular-value drops. It concludes that this is a strong case for including BQRRP as an alternative to GEQP3 in LAPACK.

Load-bearing premise

The speedup rests on the premise that a short Gaussian sketch of the input, refreshed block by block, reveals the same column-pivot order that exact pivoting would for arbitrary matrices; the paper demonstrates pivot quality only on the Kahan matrix and performance mainly on random full-rank matrices.

Editorial extensions

If this is right

  • Because BQRRP output matches GEQP3's format and the CPU version is largely in place, existing LAPACK-oriented codes could substitute it without changing data layout.
  • Thread-scaling results show BQRRP's performance grows with cores nearly as well as unpivoted GEQRF, while GEQP3's scales poorly, so the measured speedup should widen on many-core systems.
  • The block-size guidance (about n/32 for large square matrices, larger blocks for small ones) gives practitioners an immediate tuning rule.
  • On GPUs, the Householder-panel version of BQRRP is the viable one; the Cholesky-panel version is held back by the cost of reconstructing Householder vectors.
  • Pivot quality on the Kahan matrix is close to GEQP3's over almost the whole index range, so the algorithm is not merely fast but also ranks columns sensibly on at least one adversarial family.

Reading between the lines

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

  • The load-bearing assumption is inherited rather than proved here: a single Gaussian sketch, updated block by block, is assumed to expose the column order that exact pivoting would, on arbitrary inputs. A natural follow-up is a failure-probability or gap-dependent bound for the pivot ordering, since the Kahan test alone does not establish it.
  • The same sketch-driven panel pivoting could serve as a cheap column-selection primitive outside QRCP, e.g. for rank-revealing decompositions and low-rank approximations that need selected columns, where LAPACK-style pivoting is a known bottleneck.
  • Profiling shows the trailing apply-Q update, not the pivot search, is the main cost on both CPUs and GPUs; future versions are likely to gain most from fusing that update with the column permutation rather than from accelerating the sketching step.
  • Testing on a broader set of structured matrices with nearly equal column norms or clustered singular values would clarify whether the reported speedups come with the same pivot quality outside the random full-rank and Kahan cases.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 5 minor

Summary. The paper introduces BQRRP, a modular blocked randomized QR-with-column-pivoting framework for general matrices. Algorithm 1 sketches the input with a d-row Gaussian matrix and then loops over column blocks: qrcp_wide on the sketch (implemented in Algorithm 2 as LU row pivoting on the transposed sketch followed by unpivoted QR), rank estimation, column permutation, a tall unpivoted QR on the permuted panel (GEQRF or preconditioned Cholesky QR), a trailing update by the transpose Q-factor, and a deterministic sketch update (Algorithm 1, Step 24). The authors describe CPU and GPU implementations in the open-source RandLAPACK library and benchmark them against LAPACK GEQP3/GEQRF, HQRRP, and cuSOLVER. Headline results are up to 148x speedup over GEQP3 on AMD EPYC, 19x on Intel Xeon, 35-60% of GEQRF CPU performance, and about 60-65% of cuSOLVER unpivoted QR on an H100. Section 8 concludes that BQRRP presents a strong case for inclusion as an alternative to GEQP3 in LAPACK.

Significance. The paper is a substantial systems-and-engineering contribution. It provides reproducible code and scripts, detailed profiling of individual kernels, open-source implementations in RandLAPACK, and careful comparisons against external baselines, which are real strengths. The empirical speedup claims are plausible for the tested full-rank Gaussian matrices. However, the central generality claim is not yet established: the sketch-based pivot ordering is validated only on a single Kahan matrix (Section 6), and all performance tests use full-rank Gaussian inputs (Section 1.4). The stress-test concern about sketch-based pivot quality lands, and it is the main reason the LAPACK-inclusion conclusion overreaches in its current form.

major comments (4)
  1. [Algorithm 1 Step 24, Section 2.2] The load-bearing assumption is that the d-row Gaussian sketch, with d=ceil(gamma*b), reveals the column-pivot order of the original matrix well enough for arbitrary inputs. The recommended qrcp_wide in Algorithm 2 chooses columns via GETRF row pivoting on the transposed sketch, so the selection is based on largest-magnitude entries in sketch rows rather than on the column norms or rank-revealing structure of M. Remark 1 invokes the sampling-regime argument from [DG17, MQOHvdG17] rather than proving a pivot-revealing property for BQRRP. The only direct evidence is the Kahan experiment in Section 6, and the performance experiments in Section 7 use full-rank Gaussian matrices. There is therefore a concrete risk that on structured or ill-conditioned full-rank inputs the sketch-based pivot order degrades, and the Step 24 update then propagates that error. I would like to see either a proof of a pivot-revealing property or a much broader pivot-quality study, including matrices with exponentially graded column norms, several Kahan parameter settings, and ill-conditioned but full-rank matrices, before the LAPACK-inclusion conclusion in Section 8 is warranted.
  2. [Algorithm 1 Step 24, Section 2.2] The sketch update in Step 24 computes Rsk11*(R11)^{-1} and therefore requires the current block R11 to be nonsingular and reasonably well conditioned. Section 2.2 acknowledges that the update can be ill-posed when R11 is singular and mentions alternatives from [DG17, Section 4], but the RandLAPACK implementation uses a naive rank estimator and all experiments are on full-rank, well-conditioned Gaussian inputs. Ill-conditioned but full-rank matrices are not tested, and the consequences of an ill-conditioned R11 for the accuracy of later pivot decisions are not analyzed. Since BQRRP is proposed for general matrices, this case should either be analyzed or explicitly excluded from the claims.
  3. [Section 4.3, Figure 12] The GPU performance comparison excludes the cost of forming the sketch. Section 4.3 states that because RandBLAS has no GPU support, Steps 2 and 4 of Algorithm 1 are performed outside BQRRP GPU and Msk is passed in as input. Figure 12 therefore reports only the BQRRP GPU main-loop time, while the abstract and conclusion claim approximately 65% and 60% of cuSOLVER's unpivoted QR performance. For an end-to-end comparison of BQRRP GPU against cuSOLVER GEQRF, the sketch generation and application cost should be included, or the headline numbers should be explicitly qualified as excluding that cost.
  4. [Section 6, Section 8] No backward-error or numerical-stability experiments are reported. The pivot-quality metrics in Section 6, namely trailing R-norm ratios and |R(i,i)|/sigma_i, are informative but do not by themselves certify that the computed Q, R, and J from BQRRP are as accurate as those from GEQP3 in the usual sense, such as ||M - Q*R*P^T||/||M|| and orthogonality of Q. This is especially relevant for the BQRRP CQR variant, which uses preconditioning, Cholesky QR, and Householder reconstruction. Given the explicit suggestion that BQRRP be considered for inclusion in LAPACK, the manuscript should measure and report these quantities on a range of matrices.
minor comments (5)
  1. [Section 1.4, Appendix A.1] The number of repetitions is inconsistent: Section 1.4 says the best time is taken from five consecutive runs, while Appendix A.1 says twenty runs of each algorithm are performed. Please make this consistent.
  2. [Algorithm 1, line 5] The loop in Algorithm 1 runs to ceil(n/b), but the text in Section 1.3 and the termination logic in Step 21 indicate that the loop should run to ceil(n/b)-1. Please correct this bound.
  3. [Algorithms 4 and 5] Algorithm 4, Step 2, and Algorithm 5, Step 3, use zero-based loop bounds of 0:n, but for a vector of length n the loop should stop at n-1. The current bound indexes out of range.
  4. [Abstract, Section 7.1, Section 8] The headline numbers should be aligned: the abstract says 'up to two orders of magnitude' and 'approximately 65 percent' of cuSOLVER, Section 7.1 reports up to 148x on AMD and 19x on Intel, Section 7.2 reports up to 60% of cuSOLVER, and Section 8 says 'up to 140x.' Please use one consistent set of numbers.
  5. [Section 5] The text near Figure 6 contains a duplicated phrase, 'using used used'; please proofread.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: BQRRP's headline performance and pivot-quality claims are measured against external baselines, and its self-citations are supporting rather than load-bearing.

full rationale

BQRRP does not predict performance or pivot quality from a fitted model; Section 7 reports wall-clock/canonical-FLOP comparisons against LAPACK's GEQP3, GEQRF, HQRRP, and cuSOLVER's GEQRF, and Section 6 measures pivot quality against GEQP3 on the Kahan matrix. These are external benchmarks, so the headline results (up to 148x over GEQP3; 35-60% of GEQRF; roughly 60-65% of cuSOLVER GEQRF) cannot reduce by construction to the paper's own outputs. The algorithmic framework's load-bearing component, the Gaussian sketch at Algorithm 1 steps 2/4/7/24, is an inherited sampling-regime mechanism from Duersch and Gu [DG17] and Martinsson et al. [MQOHvdG17], not from a uniqueness theorem claimed by the present authors; Remark 1 only borrows terminology from the authors' survey [MDM+23, Section 2.2]. Self-citations to CQRRPT [MBM+24] occur for a naive rank estimator (Section 2.2) and for preconditioning analysis (Appendix B), but the rank estimator is needed only by the Cholesky-QR variant, and the performance experiments are run on full-rank matrices; the preconditioning analysis is independently rooted in [FGL21, Bal22, HSBY23]. The 'Wide QRCP and sketching' paragraph in Section 2.1, noting that gamma>1 cannot improve pivots when Algorithm 2 is used, is a direct property of LU-on-sketch pivoting, not a fitted assumption. The paper explicitly leaves a theoretical proof of pivot revelation as an omitted item ('One can show...', Section 2.2), and states that its block-size tuning 'is not rigorously derived' (Section 8); these are correctness and generalization limitations, not circularity. No derivation step was found in which an output quantity is equal, by definition or fitted parameter, to an input quantity.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

BQRRP's practical performance depends on the user-chosen block size b (tuned empirically to n/32) and the default sampling factor gamma=1; no other numerical constants are fitted to data. The framework's correctness draws on inherited RandNLA assumptions: the Gaussian sketch preserves pivot-relevant information, the deterministic sketch update from Duersch-Gu stays valid, and an exact rank oracle would yield a complete decomposition with probability 1. These are stated in the paper but not proved here. No invented entities are introduced beyond the algorithmic framework itself.

free parameters (3)
  • block_size b = n/32 for large matrices; max feasible for small matrices (Section 8)
    User-selected block size controls the algorithm's loop structure; the paper sweeps b from 250 to 2048 (Section 7.1) and recommends b=n/32 for large matrices, noting the tuning is empirical and 'not rigorously derived' (Section 8). Performance depends strongly on b.
  • sampling_factor gamma = 1.0
    Controls the sketch height d=ceil(gamma b). The paper states gamma=1 is the only reasonable choice when using Algorithm 2 (Section 2.1), and all experiments use gamma=1.0 (Section 7).
  • ORHR_COL block size nb = not specified, user-supplied
    Used only in the Cholesky-QR variant to set the number of column block reflectors for Householder reconstruction (Section 3.1); not central to the headline claims, but a user-chosen tuning knob.
assumptions (4)
  • domain assumption A d x n Gaussian sketch of height d=ceil(gamma b) preserves the column-norm ordering and rank profile of the input matrix well enough for pivoting decisions.
    Core of the randomized pivot selection: Algorithm 1 Step 7 performs QRCP on the sketch rather than the full matrix. The paper cites the 'sampling regime' of [MDM+23] and prior randomized QRCP work (DG17, MQOHvdG17, CQRRPT) but does not prove this for BQRRP. Entered at Algorithm 1 Steps 2 and 7.
  • domain assumption The deterministic sketch update in Step 24 (from Duersch and Gu, DG17 Section 4) keeps the sketch equal to the sketch of the updated trailing submatrix in exact arithmetic.
    BQRRP relies on this update so that subsequent iterations make rank decisions on the correct trailing sketch. The update formula is cited from prior work, not derived in this paper. Location: Algorithm 1 Step 24.
  • domain assumption With an exact rank oracle, BQRRP recovers a full decomposition of M with probability 1.
    Stated in Section 2.2: 'conditional on an event which occurs with probability 1, BQRRP returns ell = rank(M) and a full decomposition of M.' The proof is omitted; it follows the authors' and others' prior analyses but is load-bearing for the rank-revealing interpretation.
  • domain assumption The tested hardware and vendor libraries (MKL 2025.0, cuSOLVER 11.6.1.9) are representative of modern CPU and GPU environments for the measured speedups.
    The empirical claims are drawn from two CPU systems and one GPU; the paper itself cautions that subroutine choices should be re-evaluated for other architectures (Section 8). This is a generalization premise for the headline numbers.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Anatomy of High-Performance Column-Pivoted QR Decomposition." pith.science (2026). https://pith.science/paper/QK5ETVPW

@misc{pith2026250700976,
  author       = {Pith},
  title        = {Pith review of: Anatomy of High-Performance Column-Pivoted QR Decomposition},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QK5ETVPW}},
  note         = {Machine review of arXiv:2507.00976}
}
read the original abstract

We introduce an algorithmic framework for performing QR factorization with column pivoting (QRCP) on general matrices. The framework enables the design of practical QRCP algorithms through user-controlled choices for the core subroutines. We provide a comprehensive overview of how to navigate these choices on modern hardware platforms, offering detailed descriptions of alternative methods for both CPUs and GPUs. The practical QRCP algorithms developed within this framework are implemented as part of the open-source RandLAPACK library. Our empirical evaluation demonstrates that, on a dual AMD EPYC 9734 system, the proposed method achieves performance improvements of up to two orders of magnitude over LAPACK's standard QRCP routine and greatly surpasses the performance of the current state-of-the-art randomized QRCP algorithm. Additionally, on an NVIDIA H100 GPU, our method attains approximately 65 percent of the performance of cuSOLVER's unpivoted QR factorization.

Figures

Figures reproduced from arXiv: 2507.00976 by the authors.

Figure 1
Figure 1. Speedup of HQRRP [MQO￾HvdG17] (first row) and standard LA￾PACK unpivoted QR, GEQRF (second row), over the standard LAPACK QRCP, GEQP3, attained on matrices of sizes between 1,000-by-1,000 to 10,000-by￾10,000, when varying the number of OpenMP threads used. In all experi￾ments, HQRRP block size was set to 128, as suggested in [MQOHvdG17, Sec. 4.1]. Results captured on machines, described in [PITH_FULL_IMAGE:figures/… view at source ↗
Figure 2
Figure 2. Performance of the candi￾date methods for qrcp wide function in step 7 of Algorithm 1, captured on Intel and AMD systems (see Ta￾ble 1). The performance is measured via the canonical FLOP rate, relying on the FLOP count of the standard LAPACK QR function (GEQRF). Exper￾iments were conducted on matrices of size d1 × n1 and d2 × n2, with n1 = 65,536 and d1 ∈ 256 · {1, 2, 4, . . . , 32}, and n2 = 64,000 and d2 ∈ 250 · … view at source ↗
Figure 3
Figure 3. Performance of the can￾didate methods for qr tall function in step 12 of Algorithm 1, captured on Intel and AMD systems (see Ta￾ble 1). The performance is measured via canonical FLOP rate, using the FLOP count of LAPACK’s GEQRF, on matrices of sizes m1 ×k1 and m2 ×k2, with m1 = 65,536 and k1 ∈ 256 · {1, 2, 4, . . . , 32}, and m2 = 64,000 and k2 ∈ 250 · {1, 2, 4, . . . , 32}. Across all systems, we observe that Chole… view at source ↗
Figures from the paper (14 more)
Figure 4
Figure 4. Figure 4: The performance superiority of ORMQR function to the alternatives in the majority of the explored cases makes it the best option to be used in a BQRRP implementation [PITH_FULL_IMAGE:figures/full_fig_p016_4.png]
Figure 5
Figure 5. Figure 5: A visualization of how all the major components of [PITH_FULL_IMAGE:figures/full_fig_p019_5.png]
Figure 6
Figure 6. Figure 6: Percentages of BQRRP CPU runtime, occupied by its respective subroutines. The top row represents BQRRP CPU with Cholesky QR on a panel, and separately shows the percentage of runtime occupied by the preconditioned Cholesky QR and Householder restoration. The bottom row…
Figure 7
Figure 7. Figure 7: Percentages of the BQRRP GPU runtime, occupied by its respective subrou￾tines. The top row represents BQRRP GPU with Cholesky QR on a panel, and sepa￾rately shows the percentage of runtime oc￾cupied by the preconditioned Cholesky QR and Householder restoration. The bot…
Figure 8
Figure 8. Figure 8: shows the spectrum of a Kahan matrix (with default choices for the values of the tuning parameters), obtained by the Jacobi SVD function, GESVD [PITH_FULL_IMAGE:figures/full_fig_p027_8.png]
Figure 9
Figure 9. Figure 9: Pivot quality results for BQRRP with block sizes 64 and 4096 show that block size has limited impact on pivot qual￾ity. The residual-norm ratio is generally similar to that of GEQP3, diverging mainly near sharp singular value drops, especially for b = 4096. The second …
Figure 10
Figure 10. Figure 10: Performance of various QR and QRCP methods, captured on an Intel and AMD systems (see Ta￾ble 1). The execution of GEQRF and GEQP3 does not depend on the block size parameter b, and hence the per￾formance is depicted as constant. Ob￾serve that on an Intel system, both …
Figure 11
Figure 11. Figure 11: Effects of varying the num￾bers of threads on the FLOP rates in QR and QRCP methods, captured on an In￾tel and AMD systems (see [PITH_FULL_IMAGE:figures/full_fig_p030_11.png]
Figure 12
Figure 12. Figure 12: Performance of standard QR and two versions of BQRRP GPU, captured on an NVIDIA GPU (for the details on system configuration, refer to [PITH_FULL_IMAGE:figures/full_fig_p031_12.png]
Figure 13
Figure 13. Figure 13: Performance of HQRRP (first row), GEQRF (second row), and GEQP3 (third row), attained on matrices of sizes between 1,000−by−1,000 to 10,000−by−10,000, when varying the number of OpenMP threads used. Per￾formance is measured in terms of canonical FLOP rate, relying on …
Figure 14
Figure 14. Figure 14: Performance compar￾ison of HQRRP, GEQRF, and GEQP3, captured on Intel and AMD sys￾tems (see [PITH_FULL_IMAGE:figures/full_fig_p037_14.png]
Figure 15
Figure 15. Figure 15: Percentages of HQRRP runtime, occupied by its respective subroutines. Experminets were conducted on square matrices of size 32,000 × 32,000 with the HQRRP block size b taking values {5, 10, 25, 50, 125, 250, 500, 1000, 2000, 4000, 8000}. The results are captured on In…
Figure 16
Figure 16. Figure 16: Performance of various QR and QRCP methods, captured on Intel and AMD systems (see Ta￾ble 1). The execution of the GEQRF and GEQP3 functions does not depend on the block size parameter b, and hence the performance is depicted as constant. This figure concentrates on a…
Figure 17
Figure 17. Figure 17: Performance of various QR and QRCP methods, captured on Intel and AMD systems (see [PITH_FULL_IMAGE:figures/full_fig_p040_17.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 13 canonical work pages

  1. [1]

    Accessed: 2025-03-21

    [AD25] Robin Armstrong and Anil Damle, Collect, commit, expand: Efficient CPQR-based column selection for extremely wide matrices , arXiv preprint arXiv:2501.18035 (2025). Accessed: 2025-03-21. [ADO94] E. Anderson, J. Dongarra, and S. Ostrouchov, LAPACK working note 41 installation guide for LAPACK, Technical Report 37996-1301,

    arXiv 2025

  2. [5]

    [Hig22] , The big six matrix factorizations— nhigham.com ,

    [Accessed 03-Apr-2023]. [Hig22] , The big six matrix factorizations— nhigham.com ,

    work page 2023

  3. [6]

    [HQR20] HQRRP Development Team, Lapack-compatible sources for hqrrp ,

    [Accessed 15-Mar-2023]. [HQR20] HQRRP Development Team, Lapack-compatible sources for hqrrp ,

    work page 2023

  4. [7]

    [HSBY23] Andrew J

    Accessed: 2025- 05-12; Direct link: HQRRP sources. [HSBY23] Andrew J. Higgins, Daniel B. Szyld, Erik G. Boman, and Ichitaro Yamazaki, Anal- ysis of randomized Householder-Cholesky QR factorization with multisketching ,

    work page 2025

  5. [10]

    Blocked rank-revealing QR factorizations: How randomized sampling can be used to avoid single-vector pivoting

    Accessed: 2025-05-12; Direct link: MAGMA sources. [Mar15] P.-G. Martinsson, Blocked rank-revealing QR factorizations: How randomized sampling can be used to avoid single-vector pivoting , arXiv preprint arXiv:1505.08115 (2015). [MBM+24] M. Melnichenko, O. Balabanov, R. Murray, J. Demmel, M. Mahoney, and P. Luszczek, CholeskyQR with randomization and pivot...

    work page Pith review arXiv 2015

  6. [11]

    [Mil04] Bruce Miller, Kahan: Upper trapezoidal matrix for testing condition and rank estimation , National Institute of Standards and Technology,

    arXiv:2302.11474:v2. [Mil04] Bruce Miller, Kahan: Upper trapezoidal matrix for testing condition and rank estimation , National Institute of Standards and Technology,

    arXiv

  7. [14]

    NoFLA Apply Q WY lhfc blk var4

    Column three depicts results obtained on an AMD CPU using AOCL 5.0.0 (as opposed to MKL 2025.0, used elsewhere). Intel CPU +MKL AMD CPU +MKL AMD CPU +AOCL GigaFLOP/s HQRRP GigaFLOP/s GEQRF GigaFLOP/s GEQP3 m = n m = n m = n A.3 HQRRP subroutines profiling In an effort to better understand the performance gap between BQRRP and HQRRP seen in Fig- ure 11 and...

    work page 2025

  8. [15]

    for free

    Despite its simplicity and speed, Cholesky QR is rarely used in practice, as it fails 8 to provide accurate output when the numerical rank of the matrix G falls below n. This phenomenon can be mitigated with a variety of preconditioning and truncation strategies. Preconditioned Cholesky QR. The use of Cholesky QR in the context of step 12 is motivated by ...

    work page 2000

Show all 15 references
  1. [114]

    3, 275–293

    [TND+10] Stanimire Tomov, Ramesh Nath, Peng Du, Piotr Luszczek, and Jack Dongarra, MAGMA: matrix algebra on GPU and multicore architectures , International Journal of High Perfor- mance Computing Applications 24 (2010), no. 3, 275–293. [XGL17] J. Xiao, M. Gu, and J. Langou, Fa...

    2010

  2. [2004]

    [MQOHvdG17] P.-G

    Accessed: 2025-04-24. [MQOHvdG17] P.-G. Martinsson, G. Quintana-Ort´ ı, N. Heavner, and R. van de Geijn, Householder QR factorization with randomization for column pivoting (HQRRP), SIAM Journal on Scientific Computing 39 (January 2017), no. 2, C96–C115. [QOSB96] Gregorio Quin...

    2025

  3. [2019]

    [MAG20] MAGMA Development Team, zgeqp3 gpu.cpp — gpu-accelerated QR factorization with col- umn pivoting,

    Accessed: 2024-06-13; Direct link: LAPACK: ORHR COL. [MAG20] MAGMA Development Team, zgeqp3 gpu.cpp — gpu-accelerated QR factorization with col- umn pivoting,

    2024

  4. [2020]

    Accessed: 2024-06-13; Direct link: LAPACK: DGEMQRT

    [Deva] LAPACK Developers, DGEMQRT. Accessed: 2024-06-13; Direct link: LAPACK: DGEMQRT. [Devb] , DORMQR. Accessed: 2024-06-13; Direct link: LAPACK: DORMQR. [Devc] , GEQRF. Accessed: 2024-11-01; Direct link: LAPACK: GEQRF. [Devd] , GEQRT. Accessed: 2024-10-29; Direct link: LAPAC...

    2012

  5. [2021]

    Fukaya, R

    [FKN+20] T. Fukaya, R. Kannan, Y. Nakatsukasa, Y. Yamamoto, and Y. Yanagisawa,Shifted Cholesky QR for computing the QR factorization of ill-conditioned matrices , SIAM Journal on Sci- entific Computing 42 (2020), no. 1, A477–A503 (cit. on pp. 2, 19, 20). [FNY24] Takeshi Fukaya...

    2020

  6. [2022]

    Ballard, J

    [BDG+15] G. Ballard, J. Demmel, L. Grigori, M. Jacquelin, N. Knight, and H.D. Nguyen, Recon- structing Householder vectors from tall-skinny QR , Journal of Parallel and Distributed Computing 85 (2015), 3–31. IPDPS 2014 Selected Papers on Numerical and Combinatorial Algorithms....

    2015

  7. [2023]

    [Koz19] Igor Kozachenko, ORHR COL,

    arXiv:2309.05868. [Koz19] Igor Kozachenko, ORHR COL,

Pith tools

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