{"id":"111528d5-c56e-4c25-a5a5-45678e3dd437","arxiv_id":"2501.18035","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"CCEQR is a deterministic variant of Golub-Businger CPQR that provably selects the same columns as GEQP3 while running faster on wide matrices with decaying column norms.","lead":"A new algorithm, CCEQR, speeds up column-pivoted QR for very wide matrices by only examining a small candidate set of columns at each step. It gives the same selected columns as the standard LAPACK routine GEQP3, but can run up to ten times faster on spectral clustering and quantum chemistry problems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Speedup claim depends on residual-norm decay, not raw column-norm concentration; raw concentration can still force tracking all columns.","rationale":"The reader's weakest_assumption identifies the same broad risk: CCEQR's speedup is data-dependent and can disappear when the norm distribution is unfavorable. I agree with the ACCEPT verdict because the central correctness claim is well supported: Theorem 3.2 is proven in exact arithmetic, the pseudocode is reproducible, and the experiments include favorable, unstructured, and adversarial cases. The concern I raise sharpens the reader's assumption: the paper's stated condition of concentrated column norms is neither necessary nor sufficient, because the tracked-set size is governed by residual norms after each orthogonalization. The paper itself observes this in Section 4.2 and in the rare slow islands of Figure 4.1. Since the paper explicitly restricts its performance claims to 'appropriately structured problems' and demonstrates worst-case behavior in Section 4.4, this limitation does not overturn the central contribution. The c-overshoot discrepancy between Algorithm 3.3 and the proof of Theorem 3.2 is a minor but real gap in exposition; it affects the number of committed columns for small k, not the GB(k) correctness of the returned prefix, and it is not exercised in the main experiments, which use k = m or k = m/2. Therefore the reader's ACCEPT remains appropriate, with the recommendation that a revision clarify the residual-norm condition and the c cap.","tokens_in":21015,"tokens_out":33340,"duration_ms":420322,"concrete_test":"For m = 32, n = 10^6, build matrices whose column norms decay as j^{-α} for α = 1 and α = 2, but construct the largest-norm columns as linear combinations of the smallest-norm columns plus tiny orthogonal perturbations, so raw norms are strongly concentrated while residual norms after the first pivot decay slowly. Run CCEQR with ρ = 10^{-3} and k = m, and record the fraction of columns that ever enter the tracked set and the runtime ratio versus GEQP3. If the tracked fraction approaches 1 while raw norm concentration is high, the stated structural assumption is not sufficient to predict the advertised speedups.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The correctness proof (Theorem 3.2, Appendix A) is sound in exact arithmetic, so the load-bearing risk is the efficiency claim. The paper states in Section 1 and Figure 4.1 that speedups require the column norm distribution to be concentrated on a small subset, but the quantity that actually controls the tracked-set size is the sequence of residual norms after each orthogonalization, not the initial column norms. Section 4.2 and the 'islands' in Figure 4.1 already show that a matrix with strongly concentrated column norms can still force nearly every column into the tracked set: if high-norm columns lie mostly in the span of the committed skeleton, the threshold M collapses and the expand step pulls in all columns with norm above a small value. In that regime CCEQR degenerates to roughly GEQP3's work and can be slower (Figure 4.1 values as low as 0.41; Section 4.4). The paper is honest about this limitation, but no diagnostic is provided that tells a user whether a given matrix is in the favorable regime. A secondary discrepancy: Algorithm 3.3 line 2 does not cap c at k-s, while the proof of Theorem 3.2 asserts c is in [1, k-s]; for k < m with flat norms, c can overshoot (e.g., orthonormal columns), so the pseudocode can commit more than k columns and the proof's 's_T = k' statement is not literally true. This does not invalidate GB(k) correctness of the returned prefix, but it is an unaddressed mismatch.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces CCEQR, a deterministic variant of the Golub-Businger CPQR algorithm aimed at matrices with far more columns than rows. The algorithm proceeds in cycles: a \"collect\" step selects a small candidate block from the tracked columns by residual norm; a \"commit\" step uses a GEQP3 factorization of the candidates to extend the skeleton by a provably safe number of columns; an \"expand\" step restores the invariant that the maximum tracked residual dominates all untracked column norms by moving sufficiently large untracked columns into the tracked set. The main theoretical claim is Theorem 3.2: the permutation returned by CCEQR is equivalent to that of Algorithm 2.1 in the sense that Q* A(:,p) is in GB(k) form for some unitary Q. Experiments on spectral demixing and DFT/Wannier-basis problems report order-of-magnitude speedups over GEQP3 in favorable regimes, while Gaussian and adversarial Hadamard matrices show comparable or slower runtimes. A Julia implementation and reproduction code are provided.","tokens_in":21329,"tokens_out":12858,"duration_ms":141656,"significance":"If the correctness claim holds, this is a useful contribution to numerical linear algebra: it gives a deterministic, blocked CPQR-based column selection method for extremely wide matrices, with a self-contained proof in exact arithmetic and an honest experimental evaluation. The paper clearly identifies favorable and unfavorable regimes, and it provides open-source code. The central theorem is defensible, but the pseudocode and proof contain local inconsistencies that must be fixed. The efficiency benefit is heuristic and structure-dependent, not a worst-case guarantee, and the paper is appropriately transparent about this.","major_comments":[{"comment":"The quantity c defined in Algorithm 3.3, line 2 as c = max{i>=1 : |bR(i,i)|^2 >= delta or mu} is not capped at k-s, even though the proof of Theorem 3.2 asserts c is in [1, k-s] and uses this to conclude that s_T = k for some T <= k. Since bR can have up to min(m-s,b) nonzero diagonals and b may exceed k-s, c can overshoot the remaining skeleton size; for example, with k=1 and two orthonormal candidate columns, c can equal 2. The returned prefix is still GB(k) when s_T > k, so the theorem is repairable, but the pseudocode and proof should be aligned, for instance by setting c <- min(c, k-s) after line 2 of Algorithm 3.3 or by explicitly allowing s_T >= k in the induction.","section":"Algorithm 3.3 / Theorem 3.2"},{"comment":"The pseudocode does not match the text and the proof in two places. First, Section 3.2 states that the first cycle sets t <- b+1, but Algorithm 3.2 line 5 sets t <- b; since delta is computed before line 5, the proof's characterization of delta as the maximum over non-candidate tracked columns no longer matches the described algorithm. Second, Algorithm 3.3 line 11 reads 'c <- c - t' and should read 't <- t - c'; as printed, the tracked-set size is never reduced after a commit, which would break the partition invariant used by Lemma 3.1 and the subsequent expand step. These are local fixes, but they are necessary for the printed pseudocode to implement the proven algorithm.","section":"Algorithms 3.2 and 3.3"}],"minor_comments":[{"comment":"The paper states that the favorable regime is characterized by column-norm concentration, but the quantity that actually controls the tracked-set size is the decay of residual norms after orthogonalization; Figure 4.1's own 'islands' show that strong initial concentration can still force nearly all columns into the tracked set. The paper discusses this honestly in Section 4.1, but it would help to state explicitly in Section 1 that the column-norm condition is a heuristic, and to mention a possible diagnostic such as monitoring M/t.","section":"Section 1 and Figure 4.1"},{"comment":"Line 7 of Algorithm 3.5 calls 'Exand' instead of 'Expand'; this typo should be corrected.","section":"Algorithm 3.5"},{"comment":"The theorem states 'Let p in [n]^k be the permutation vector returned by Algorithm 3.5', but Algorithm 3.5 returns a permutation vector of length n, not k. Please clarify the notation so that p denotes the full permutation vector and A(:,p(1:k)) the selected columns.","section":"Theorem 3.2"},{"comment":"In Appendix B, the text first says 'By construction, V2 is upper-triangular with unit diagonal' and then, in the proof of Lemma B.1, says 'Because V2 is a lower-triangular m x (s+c) matrix with unit diagonal'. The latter is correct for Householder vectors; the former statement should be fixed.","section":"Appendix B"},{"comment":"The runtime plots report only medians and no measure of spread. Since CCEQR's runtime is highly variable in the island regime (Figure 4.1), reporting error bars or at least stating the variability would strengthen the experimental claims.","section":"Section 4"},{"comment":"The text says 'a system of m elections' where 'electrons' is meant; please correct this typo.","section":"Section 4.2"}],"recommendation":"minor_revision","confidential_remarks":"The manuscript is a good fit for a numerical linear algebra journal. The correctness proof is self-contained and does not rely on prior work of the authors; the self-citations appear only as motivating applications. Once the c-cap issue and the pseudocode typographical errors are corrected, the central claims are sound. The efficiency claim is conditional on problem structure, but the paper is transparent about this and includes adversarial experiments, so I do not see it as a blocker."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"CCEQR is worth your time. It is a new deterministic blocking strategy for Golub–Businger CPQR that provably reproduces the same permutation while shifting most Householder work from BLAS-2 to BLAS-3. I checked the main equivalence proof, Theorem 3.2 with Lemma 3.1; it is self-contained and the case analysis in Appendix A is consistent. The paper also ships Julia code, and the experiments cover the two intended applications, structured random matrices, and an honest adversarial example where CCEQR is slower than GEQP3. That set of evidence is more than most papers in this area provide.\n\nThe novel piece is the collect–commit–expand mechanism itself: unlike HQRRP it is deterministic, and unlike Quintana-Orti et al. it attacks the wide-matrix bottleneck directly. The correctness claim does not depend on any norm-concentration assumption, and the proof is not resting on prior work from the same group. Self-citations appear only as motivating applications, which is fine.\n\nThe soft spots are real but not load-bearing. The paper frames the favorable case as concentrated column norms, but the quantity that actually controls the tracked-set size is the residual-norm sequence after each orthogonalization. The 'islands' in Figure 4.1 and the cycle-count spike in Figure 4.4 are exactly this effect: a matrix with concentrated norms can still force nearly all columns into the tracked set if the large columns lie mostly in the span of the committed skeleton. The authors are transparent about this, but they give no diagnostic that tells a user whether a given matrix is in the fast regime. That is a usability gap for a method whose whole selling point is speed.\n\nThere is also a small mismatch between pseudocode and proof: Algorithm 3.3's c is not capped at k−s, and Theorem 3.2's proof asserts the skeleton lands exactly at k. With flat norms and large rho, c can overshoot and the algorithm terminates with s>k; the returned prefix is still a valid GB(k) permutation, so this is not a correctness failure, but the 's_T=k' statement is not what the code does. Minor pseudocode typos and medians without error bars do not change the picture.\n\nWho gets value: anyone working on column subset selection for very wide matrices, especially spectral clustering, DEIM, and Wannier localization, and anyone comparing deterministic versus randomized pivoting. It deserves a serious referee; I would expect acceptance after minor revisions that tighten the termination statement and add a practical note on when to expect the fast regime.","headline":"Genuinely new deterministic CPQR blocking with a solid equivalence proof; speedups are real in the intended regime, but the favorable-regime condition is under-specified.","tokens_in":21865,"tokens_out":4502,"would_cite":true,"duration_ms":285269,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F25","65F30","62H30","82-08"],"pacs":[],"model":"deepseek-v4-flash","headline":"CCEQR is a deterministic variant of column-pivoted QR that provably selects the same columns as the Golub-Businger algorithm while shifting most work to level-3 BLAS, giving order-of-magnitude speedups on very wide matrices with decaying…","keywords":["column subset selection","column-pivoted QR","Golub-Businger algorithm","GEQP3","compact WY form","level-3 BLAS","spectral clustering","Wannier basis"],"falsifier":"Run Algorithm 3.5 and Algorithm 2.1 in exact arithmetic on a fixed rational matrix and compare the permutations; if CCEQR's $p$ cannot be completed to GB($k$) form by some unitary $Q$, Theorem 3.2 is false. For the speed claim, take a family of wide matrices with a fixed rate of column-norm decay and let $n$ grow; if the fraction of columns that ever become tracked does not shrink, or the runtime ratio of GEQP3 to CCEQR stops growing with $n$, the advertised speed advantage fails.","tokens_in":20816,"feed_emoji":"⚡","tokens_out":11188,"duration_ms":94718,"temperature":0.7,"pith_summary":"The paper proposes CCEQR, a column selection routine for matrices with far more columns than rows. Column subset selection asks for a small set of representative columns whose span approximates the whole matrix, and the standard workhorse for this is Golub-Businger column-pivoted QR. CCEQR provably returns the same column choice as Golub-Businger, but instead of applying every Householder reflector to every column it cycles through collect, commit, and expand steps, limiting slow matrix-vector (BLAS-2) work to a small candidate block and pushing most updates through fast matrix-matrix (BLAS-3) operations. On spectral clustering and Wannier-basis problems, where column norms decay rapidly, the authors report runtimes up to roughly 24 times faster than the LAPACK implementation, while on unstructured or equal-norm matrices CCEQR remains within about a factor of two. The equivalence proof is deterministic and needs no structural assumption, so the speed advantage is the only part that depends on the problem's column-norm profile.","feed_headline":"Same columns as LAPACK's GEQP3, an order of magnitude faster","feed_subtitle":"CCEQR keeps the tracked column set small, shifting most work to BLAS-3 and speeding up clustering and DFT test problems.","key_machinery":"At the core is the collect-commit-expand cycle, which splits columns into three blocks: committed skeleton columns, tracked columns whose residual norms after projecting out the skeleton are maintained, and untracked columns for which only the original norm is stored. The collect step sorts tracked columns by residual norm, takes the top fraction $\\rho$ as candidates, and runs GEQP3 on just that candidate block. The commit step promotes candidates using the threshold $c=\\max\\{i : |\\hat R(i,i)|^2 \\ge \\max(\\delta,\\mu)\\}$, where $\\hat R$ is the candidate block's R-factor, $\\delta$ is the largest non-candidate tracked residual, and $\\mu$ is the largest untracked norm; this condition is exactly what prevents a non-candidate from overtaking the greedy order. New Householder reflectors are folded into the global unitary factor in compact WY form $Q = I - VTV^*$, so later applications are level-3 BLAS operations, and the expand step pulls in all untracked columns whose norms exceed the new tracked maximum, restoring invariant (3.1) that guarantees the next cycle commits at least one column. Together these pieces reproduce the Golub-Businger permutation without ever updating all $n$ columns at every pivot step.","core_discovery":"The central claim is Theorem 3.2: on any matrix, in exact arithmetic, the permutation vector returned by CCEQR is equivalent to the one computed by the Golub-Businger algorithm, meaning there exists a unitary $Q$ such that $Q^*A(:,p)$ is in GB($k$) form. Equivalently, CCEQR selects exactly the same skeleton columns as GEQP3. It does this by maintaining an invariant: after each cycle, the largest residual norm among tracked columns is at least as large as any untracked column's original norm, and the commit step only accepts a candidate column when its diagonal R entry dominates both the best non-candidate residual and the best untracked norm. The efficiency comes from limiting BLAS-2 Householder application to the small candidate block and applying BLAS-3 operations only to the tracked set; a CSSP-only mode further avoids forming the full R. On structured test problems from spectral demixing and density functional theory, the reported speedups over GEQP3 reach roughly one to two orders of magnitude, while on Gaussian random and adversarial Hadamard matrices CCEQR remains within about a factor of two.","pith_inferences":["A natural extension the paper leaves implicit: the gap between the largest candidate residual and the largest non-candidate residual controls how many columns each cycle can commit, and a future implementation could measure this gap online and adapt $\\rho$ or the expansion threshold accordingly.","Because untracked columns enter CCEQR only through their original norms, the algorithm is plausibly adaptable to streaming or out-of-core settings where columns are read once and then discarded; the paper does not discuss this extension.","The equivalence theorem holds in exact arithmetic; in floating point, nearly tied column norms such as the Hadamard construction with machine-epsilon tie-breaking are the boundary where CCEQR and GEQP3 could diverge, so downstream applications with ties should compare the two choices empirically."],"forward_implications":["Applications that currently call GEQP3 for column selection, such as spectral clustering and DEIM-based model reduction, can switch to CCEQR without changing the selected columns, as long as only the permutation is needed.","For matrices with rapidly decaying column norms, the speedup grows as the number of columns grows: in the spectral demixing tests, CCEQR beats GEQP3 once $n$ reaches about $10^4$ columns, with reported ratios up to roughly 15 in the CSSP-only setting.","A full CPQR factorization can still be produced by applying the final reflections to the untracked columns, and the authors report smaller but still positive speedups in this mode.","The user parameter $\\rho$, which controls candidate block size, has a broad plateau of good values, but very small or very large values degrade performance by inflating tracked sets or candidate blocks.","On unstructured Gaussian matrices CCEQR retains the same $O(n)$ scaling as GEQP3 for fixed row count and is only modestly slower, so the method does not sacrifice asymptotic scaling in the worst case."],"supporting_citations":[{"why":"It defines the Golub-Businger column-pivoted QR algorithm whose column choice CCEQR is proved to reproduce.","marker":"[5]"},{"why":"It supplies the compact WY representation that lets CCEQR apply blocked Householder reflectors with level-3 BLAS.","marker":"[34]"},{"why":"It introduces the row-restricted BLAS-3 CPQR strategy that CCEQR reframes for matrices with far more columns than rows.","marker":"[31]"},{"why":"It generates the spectral clustering column-selection problem that provides the first set of test matrices and the speedup comparison.","marker":"[10]"},{"why":"It generates the density-functional-theory Wannier-basis problem that provides the alkane and water test matrices for the large-scale speedups.","marker":"[9]"},{"why":"It is the representative randomized blocked CPQR method whose sketched pivot choices CCEQR contrasts with its deterministic equivalence to Golub-Businger.","marker":"[29]"}],"fun_headline_variants":["CCEQR: deterministic CPQR with GEQP3-equivalent pivots","Same skeleton columns as LAPACK, but BLAS-3 speed","Faster CPQR for wide matrices: CCEQR matches GEQP3 pivots","Collect, commit, expand: CPQR column selection at BLAS-3 speed","CCEQR: provably same pivots as GEQP3, with BLAS-3 efficiency"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The speed advantage rests on the data having most column-norm mass concentrated in a small number of columns; when many columns have comparable norms, the expand step pulls almost all columns into the tracked set and CCEQR runs slower than GEQP3.","fun_headline_variants_meta":{"raw":{"variants":["CCEQR: deterministic CPQR with GEQP3-equivalent pivots","Same skeleton columns as LAPACK, but BLAS-3 speed","Faster CPQR for wide matrices: CCEQR matches GEQP3 pivots","Collect, commit, expand: CPQR column selection at BLAS-3 speed","CCEQR: provably same pivots as GEQP3, with BLAS-3 efficiency"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000389,"raw_usage":{"total_tokens":2075,"prompt_tokens":993,"completion_tokens":1082,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":609,"completion_tokens_details":{"reasoning_tokens":984}},"tokens_in":609,"tokens_out":1082,"duration_ms":184267,"temperature":1.0,"reasoning_tokens":984,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T00:53:40.482656+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 3.5 and Algorithm 2.1 in exact arithmetic on a fixed rational matrix and compare the permutations; if CCEQR's $p$ cannot be completed to GB($k$) form by some unitary $Q$, Theorem 3.2 is false. For the speed claim, take a family of wide matrices with a fixed rate of column-norm decay and let $n$ grow; if the fraction of columns that ever become tracked does not shrink, or the runtime ratio of GEQP3 to CCEQR stops growing with $n$, the advertised speed advantage fails.","supporting_citations":[{"cited_title":"Businger and G","cited_arxiv_id":null,"evidence_quote":"It defines the Golub-Businger column-pivoted QR algorithm whose column choice CCEQR is proved to reproduce."},{"cited_title":"Schreiber and C","cited_arxiv_id":null,"evidence_quote":"It supplies the compact WY representation that lets CCEQR apply blocked Householder reflectors with level-3 BLAS."},{"cited_title":"Quintana-Ort´ı, X","cited_arxiv_id":null,"evidence_quote":"It introduces the row-restricted BLAS-3 CPQR strategy that CCEQR reframes for matrices with far more columns than rows."},{"cited_title":"Damle, V","cited_arxiv_id":null,"evidence_quote":"It generates the spectral clustering column-selection problem that provides the first set of test matrices and the speedup comparison."},{"cited_title":"Damle, L","cited_arxiv_id":null,"evidence_quote":"It generates the density-functional-theory Wannier-basis problem that provides the alkane and water test matrices for the large-scale speedups."},{"cited_title":"Martinsson, G","cited_arxiv_id":null,"evidence_quote":"It is the representative randomized blocked CPQR method whose sketched pivot choices CCEQR contrasts with its deterministic equivalence to Golub-Businger."}],"review_version":1}