{"id":"365a9ec6-7582-44bb-9b21-251c256e52f6","arxiv_id":"2507.00976","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A randomized, modular QR-with-column-pivoting framework (BQRRP) is shown to run up to two orders of magnitude faster than LAPACK's GEQP3 on AMD CPUs and near unpivoted-QR speed on an H100 GPU, in the authors' open-source implementation.","lead":"The paper presents BQRRP, a new modular framework for QR matrix factorization with column pivoting that lets users pick the best subroutines for their hardware. On modern CPUs and GPUs, the open-source implementation runs much faster than the standard LAPACK pivoted QR routine and approaches the speed of unpivoted QR, which could make pivoted QR practical in high-performance computing.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Sketch-based pivot ordering is validated only on Kahan and Gaussian inputs; without broader numerical testing, the claim that BQRRP is a general GEQP3 alternative is not established.","rationale":"The reader's weakest-assumption analysis identifies exactly the load-bearing premise: the Gaussian sketch, updated via Algorithm 1 Step 24, must preserve enough information about the original matrix's column-pivot order for arbitrary inputs. I agree with that identification. The paper provides only one pivot-quality experiment (Kahan, Section 6) and all performance tests use full-rank Gaussian matrices (Section 1.4, Section 7). The recommended qrcp_wide is LU with partial pivoting applied to the sketch transpose (Algorithm 2), and the sketch height is only d=b; this is a very lossy projection for wide matrices, and no theorem in the paper guarantees that the resulting pivot order is rank-revealing for general inputs. A specific additional mechanism is the Step 24 update's dependence on R11^{-1}, which becomes ill-conditioned when the current block is full-rank but ill-conditioned; the paper does not test such matrices. The GPU timing omission and the empirically tuned block size are secondary issues; even if those were fixed, the pivot-generalization gap would remain. Because this is a missing-evidence problem rather than a demonstrated counterexample, CONDITIONAL remains the right verdict: the performance engineering is credible and well-documented, but the numerical-reliability claim requires a broader experimental or analytic demonstration before LAPACK inclusion can be recommended. The proposed concrete test would either supply that evidence or reveal the failure mode.","tokens_in":29169,"tokens_out":6448,"duration_ms":102304,"concrete_test":"Run BQRRP HQR and CQR on a suite of full-rank matrices A = U Σ V^T with U,V random orthogonal and Σ diagonal with prescribed singular values: (i) exponential decay, (ii) clustered singular values, (iii) one small singular value (e.g., 1e-8) with the rest 1, at n=8192, b=256 and 1024. For each matrix, compute the Section 6 pivot-quality metrics: max_i ||R(i:,i:)||_F (BQRRP)/||R(i:,i:)||_F (GEQP3) and max_i |R(i,i)|/σ_i. If any max residual ratio exceeds 10 or max diagonal ratio exceeds 10× GEQP3's, then the sketch-based pivot ordering fails to generalize, and the paper's general-matrix claim is falsified.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that BQRRP is a practical replacement for GEQP3 depends on the sketch at Algorithm 1 Steps 2/7/24 revealing the column-pivot order of the original matrix. With the recommended configuration (γ=1, d=b, Algorithm 2), the pivot decision is made by GETRF on a b-row random projection of an n-column trailing matrix. This is a sampling-regime argument (Remark 1) carried over from [DG17, MQOHvdG17], not proved here, and the only direct evidence is the Kahan experiment (Section 6) plus full-rank Gaussian performance runs (Section 1.4, Section 7). There is a concrete failure mode: for a matrix whose important columns are not the largest-norm columns of the sketch, LU-with-partial-pivoting on the sketch can select a column that is poor for rank revelation, and the Step 24 update then propagates that error. Moreover, R11 in the update is only guaranteed nonsingular when the block is full-rank and well-conditioned; the paper tests only full-rank Gaussian and Kahan inputs, leaving ill-conditioned but full-rank matrices untested. Without either a proof of the pivot-revealing property for general inputs or a broader empirical study, the LAPACK-inclusion conclusion overreaches.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":29396,"tokens_out":7913,"duration_ms":97297,"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":[{"comment":"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.","section":"Algorithm 1 Step 24, Section 2.2"},{"comment":"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.","section":"Algorithm 1 Step 24, Section 2.2"},{"comment":"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.","section":"Section 4.3, Figure 12"},{"comment":"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.","section":"Section 6, Section 8"}],"minor_comments":[{"comment":"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.","section":"Section 1.4, Appendix A.1"},{"comment":"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.","section":"Algorithm 1, line 5"},{"comment":"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.","section":"Algorithms 4 and 5"},{"comment":"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.","section":"Abstract, Section 7.1, Section 8"},{"comment":"The text near Figure 6 contains a duplicated phrase, 'using used used'; please proofread.","section":"Section 5"}],"recommendation":"major_revision","confidential_remarks":"This is a strong systems paper with reproducible code and clear benchmarking methodology. The main risk is the gap between the empirical performance claims on Gaussian matrices and the general-purpose LAPACK-replacement conclusion; the missing pivot-quality and numerical-stability evidence is the key obstacle. I would not reject the paper, but the LAPACK-inclusion claim should be softened or supported by additional experiments before acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this paper is not a theoretical breakthrough; it is a careful systems engineering result. The BQRRP framework modularizes QRCP construction, and the CPU/GPU implementations in RandLAPACK are real, released, and benchmarked against GEQP3, GEQRF, and HQRRP. The headline numbers hold on the inputs they test: up to ~148x over GEQP3 on AMD, ~19x on Intel, 35-60% of unpivoted GEQRF on CPUs, and 60-65% of cuSOLVER unpivoted QR on an H100. Those are credible figures.\n\nWhat is genuinely new: the LU-based wide QRCP subroutine (Algorithm 2), the in-place storage design, the modular framework itself, and the detailed profiling of subroutine choices on two modern CPU architectures and a GPU. The paper also does a service by documenting that HQRRP's performance stagnates on current hardware, which is a useful data point for the community.\n\nThe soft spots are real but not fatal. Pivot quality is validated only on the Kahan matrix (Section 6), and all performance tests use full-rank Gaussian matrices (Section 1.4). The sketch-based pivot ordering at Algorithm 1 steps 2/7/24 is inherited from prior RandNLA work and is not proved here; the stress-test concern about failure on structured or ill-conditioned inputs is legitimate. The GPU timings exclude sketch-formation cost (Section 4.3), which is part of the advertised algorithm. There is also no backward-error analysis, which matters for a LAPACK-inclusion claim. These are addressable with additional experiments, not internal contradictions. The paper is honest about the block-size recommendation being empirically tuned, which I appreciate.\n\nThe central performance claims are solid on the tested regime. The conclusion that BQRRP is a strong candidate for LAPACK inclusion overreaches relative to the evidence: I would want at least one ill-conditioned structured test beyond Kahan, a backward-error experiment, and transparent GPU timing including sketching before signing off on that.\n\nThis paper is for numerical software engineers and RandNLA researchers who care about high-performance factorizations. It deserves a serious referee, and I would accept it for review with major revision requests focused on numerical evidence. The code and benchmarks are a genuine contribution that the community will build on.","headline":"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.","tokens_in":30019,"tokens_out":2240,"would_cite":true,"duration_ms":27591,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F25","68W20","65Y05"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["QR factorization","column pivoting","randomized numerical linear algebra","blocked algorithms","LU-based QRCP","GPU linear algebra","Kahan matrix","LAPACK GEQP3"],"falsifier":"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.","tokens_in":28947,"feed_emoji":"⚡","tokens_out":9296,"duration_ms":93591,"temperature":0.7,"pith_summary":"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.","feed_headline":"Randomized pivoted QR hits 148x speedup over LAPACK","feed_subtitle":"A sketch-driven block framework matches standard pivot quality while running near unpivoted QR speed.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the randomized QRCP approach and the deterministic sketch-update formula used in Algorithm 1's step 24.","marker":"[DG17]"},{"why":"Defines HQRRP, the randomized QRCP baseline that BQRRP's CPU implementation is compared against and surpasses.","marker":"[MQOHvdG17]"},{"why":"Is the authors' prior CQRRPT algorithm, the direct predecessor that contributes the rank estimator, preconditioning idea, and pivot-quality metrics.","marker":"[MBM+24]"},{"why":"Documents the BLAS-3 limitation of Householder QRCP that motivates replacing GEQP3-style pivoting.","marker":"[QOSB96]"},{"why":"Provides earlier blocked rank-revealing QRCP designs that the block-level framework builds on.","marker":"[BQO98b]"},{"why":"Supplies the Householder-vector reconstruction algorithm used by the Cholesky-QR variant of BQRRP.","marker":"[BDG+15]"},{"why":"Gives the bound relating diagonal R entries to singular values that the paper uses to interpret the pivot-quality metric.","marker":"[Hig21]"}],"fun_headline_variants":["Randomized pivoted QR: 148x speedup, near unpivoted performance","Block QRCP via random sketch: up to 148x faster than LAPACK","BQRRP: pivoted QR at 60-65% of unpivoted speed, 148x LAPACK gain","Sketch-based pivoting accelerates QRCP by 2 orders of magnitude"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Randomized pivoted QR: 148x speedup, near unpivoted performance","Block QRCP via random sketch: up to 148x faster than LAPACK","BQRRP: pivoted QR at 60-65% of unpivoted speed, 148x LAPACK gain","Sketch-based pivoting accelerates QRCP by 2 orders of magnitude"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001077,"raw_usage":{"total_tokens":4480,"prompt_tokens":890,"completion_tokens":3590,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":506,"completion_tokens_details":{"reasoning_tokens":3504}},"tokens_in":506,"tokens_out":3590,"duration_ms":28414,"temperature":1.0,"reasoning_tokens":3504,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T21:01:51.067321+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}