{"id":"b0f68487-10dd-40ff-a9ef-312dfc265e89","arxiv_id":"2411.17671","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"RQR, a pole-swapping eigenvalue algorithm, is competitive with Francis's bulge-chasing QR algorithm, being faster and slightly more accurate on the tested matrices.","lead":"The RQR algorithm computes eigenvalues by swapping poles instead of chasing bulges, a fresh alternative to the classic QR algorithm. In tests, it runs about 17 to 29 percent faster and gives smaller backward errors than LAPACK's QR eigensolver on the problems studied.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Backward stability of the unproven Q-first swap variant (Section 2, |λ1| < |λ2|) is the load-bearing gap: if the asserted duality with the Z-first case fails, RQR's accuracy and speed advantages lack foundation.","rationale":"The reader's weakest_assumption is exactly the unproven duality of the Q-first swap variant. In good faith, the paper is a clear algorithm paper with supportive experiments, and I do not see an internal inconsistency in the Z-first branch or in the type-I moves. The weakest point is the single sentence in Section 2 that asserts numerical equivalence with the analyzed case without proof. This is load-bearing because the algorithm's backward stability, and hence its reported accuracy and reliability, depends on every swap being stable. The comparison to ZLAHQR is appropriately limited to the single-shift regime and the authors disclose the missing multishift/AED features, so I do not treat that as a separate objection to the central claim as scoped. The concrete test combines an analytical re-derivation with a targeted numerical stress test of the swap. If the duality holds, the paper's claims stand for the tested regime, matching the reader's CONDITIONAL verdict.","tokens_in":10336,"tokens_out":13621,"duration_ms":122579,"concrete_test":"Re-derive the backward error bound for the |λ1| < |λ2| branch by following the proof in [9] after applying the reversal conjugation J(·)*J to the pencil, tracking the constants in each turnover/fusion step; if any constant grows with the condition number of the 2×2 active pencil, the duality claim fails. In parallel, implement the isolated Q-first swap and run 10^6 random 2×2 Hessenberg subpencils with 10^{-16} ≤ |λ1|/|λ2| ≤ 1, measuring the relative backward error of the transformed pencil; if the median exceeds a few units of machine epsilon, the asserted stability is refuted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 2 introduces two swap variants. For |λ1| ≥ |λ2|, Z is computed first and the error analysis of Camps et al. [9] applies directly. For |λ1| < |λ2|, Q is computed first via H = s_{j−1}A_active − a_{j,j−1}U_active, and the paper states only that “The analysis in [9] does not mention this case explicitly, but this is dual to the ‘Z-first’ method shown above and has the same numerical properties.” No proof or citation to a specific theorem is given. The duality is not trivial: conjugation by the reversal permutation is needed to map the Q-first variant to the Z-first variant, and the turnover that passes a core through the unitary Hessenberg factor U runs in the opposite direction. If that reversal changes the roundoff behavior—for example, if the intermediate H entries suffer cancellation when a_{j,j−1} and s_{j−1} are large but λ1 is small—the per-swap backward error could exceed O(eps). Since every RQR iteration relies on these swaps, and the reported accuracy advantage (1.5–2× smaller backward error, Table 5.1) is attributed to fewer roundoff-producing iterations, an unstable swap branch would invalidate the central competitiveness claim for the matrices that trigger it. This is the most load-bearing assumption because it is both explicitly unproven in the manuscript and essential to the algorithm's numerical reliability.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the RQR algorithm, a pole-swapping alternative to Francis's bulge-chasing QR algorithm for the standard eigenvalue problem. It adapts the earlier RQZ algorithm to operate on a pencil A - λU, where U is a unitary upper Hessenberg matrix stored compactly as a product of core transformations. The central ingredient is a swap of two adjacent poles, with two variants depending on the relative magnitudes of the two eigenvalues: a Z-first variant for |λ1| ≥ |λ2| and a Q-first variant for |λ1| < |λ2|. The paper also describes type I moves that insert arbitrary poles, and it presents a Fortran implementation (ZLAHPS) compared against LAPACK's ZLAHQR. Numerical experiments on random matrices and Matrix Market test matrices indicate that the RQR algorithm is on average about 17% faster for matrices of size less than 75 and about 29% faster for larger matrices, with backward errors smaller by a factor of 1.5 to 2. The authors state that these results are a preliminary indication, since their implementation uses only single shifts and does not include multishift or aggressive early deflation.","tokens_in":10632,"tokens_out":4968,"duration_ms":45882,"significance":"If the stability and performance claims hold, RQR provides a genuinely distinct algorithmic approach to the standard eigenvalue problem, one that is not a minor variant of Francis's QR but a structurally different method based on pole swapping. The paper is careful in its derivation of the two swap cases and honest about the current limitations of the implementation, explicitly noting that no multishift variant or aggressive early deflation has been implemented. A notable strength is that the central performance claims are tested against an independent external implementation, LAPACK's ZLAHQR, on a range of matrix sizes and on public test matrices, rather than only on synthetic examples. The observed speedups and backward-error improvements are consistent across the tested cases, which gives credibility to the claim that the algorithm is competitive in the single-shift regime.","major_comments":[{"comment":"The Q-first swap variant is asserted to be backward stable with the sentence: \"The analysis in [9] does not mention this case explicitly, but this is dual to the 'Z-first' method shown above and has the same numerical properties.\" No proof or specific theorem is given. This is load-bearing because every RQR iteration uses this branch for many eigenvalue configurations, and the paper attributes RQR's smaller backward errors to fewer roundoff-producing iterations. If the duality fails—for example, if the construction of H = s_{j-1}A_active - a_{j,j-1}U_active suffers from cancellation in some configurations—the per-swap backward error could exceed O(eps), undermining both the accuracy and the speed claims. Please provide a proof of backward stability for the Q-first variant, or a precise reduction to the analysis in [9], or explicitly restate the claim as an empirically supported observation rather than a proven property.","section":"Section 2, case |λ1| < |λ2|"},{"comment":"The reported speedups (17% and 29%) and backward-error factors (1.5 to 2) are presented as averages without any measure of spread, such as standard deviations or confidence intervals. Since the differences are modest in magnitude and the paper draws quantitative conclusions from them, reporting the variance across the 100 random trials at each size would substantially strengthen the evidence. As written, the reader cannot assess whether the observed improvements are statistically robust or within trial-to-trial noise. This is not a fundamental flaw, but it is a missing piece in the quantitative support for the central claim.","section":"Section 5, Figure 5.1 and Table 5.1"}],"minor_comments":[{"comment":"The abstract states that RQR \"is competitive with Francis's bulge-chasing QR algorithm,\" while the concluding paragraph of Section 5 calls the experiments \"a preliminary indication.\" The strength of the claim in the abstract should be aligned with the caveats about the single-shift implementation and the limited comparison scope (ZLAHQR only, not the full LAPACK multishift routines).","section":"Abstract / Section 5"},{"comment":"The middle panel is labeled \"Avg. Accuracy Factor\" but the caption does not define how this factor is computed. Please state explicitly that it is the ratio of QR backward error to RQR backward error (or the inverse), so the reader can interpret the values around 0.5–0.7.","section":"Figure 5.1"},{"comment":"The type I move at the bottom is described only as \"analogous\" and left to the reader. Since this move is part of the algorithm's iteration, a short explicit description would improve the paper's self-containedness, especially for readers not deeply familiar with the RQZ literature.","section":"Section 2, moves of type I"},{"comment":"The table uses green and red coloring to indicate better and worse entries, but this coloring will not be visible in grayscale print. Consider adding a symbol (e.g., asterisks) or a note describing which entries are better, so the information is accessible in all formats.","section":"Table 5.2"},{"comment":"Reference [2] is a GitHub repository URL; if a specific version or commit was used for the modified turnover routines, it would be helpful to cite a release or DOI to improve reproducibility.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The paper makes a solid algorithmic contribution and the experimental work is honest and careful. The main gap is the unproved backward-stability claim for the Q-first swap variant in Section 2. This is not a reason to reject, because the experiments provide empirical evidence that the algorithm works, and the gap is local and fixable. However, it is load-bearing for the theoretical backing of the paper, so I recommend major revision rather than minor revision. The self-citation pattern is appropriate given that the algorithm builds on the authors' own RQZ work. The paper fits the scope of math.NA well."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"RQR is a genuine new algorithm, and the numerical results in the single-shift regime support the authors' claim: it is competitive with Francis's QR, a bit faster, and slightly more accurate. The key idea - adapting pole swapping to the standard problem by letting the unitary Hessenberg factor U drift from I and using a finite pole at the bottom instead of the infinite pole that reduces to QR - is clearly explained, and the experiments are honest. The comparison to LAPACK's ZLAHQR is fair for the small-matrix case, and the authors explicitly note that the larger-matrix numbers do not yet account for multishift and aggressive early deflation.\n\nThe soft spot the stress test flags is real but, in my view, minor rather than load-bearing. In Section 2, the |lambda1| < |lambda2| branch computes Q first, and the paper claims this is dual to the Z-first case with the same numerical properties, citing [9] for the other branch only. No proof or even a sketch of the duality is given. If I were refereeing, I would ask for a lemma or a pointer to a specific theorem. But I do not see an obvious reason the duality fails: the formulas are mirror images under reversal, and the computed backward errors in the experiments - which must exercise both branches - are consistently at machine precision. So the concern is more about documentation than correctness.\n\nTwo other limitations are worth noting. First, the code is not publicly available, which makes reproduction harder. Second, the backward error advantage (1.5-2x) sits between about 1e-15 and 2.5e-15; that is at the noise floor, so it is a theoretical point more than a practical one. The iteration-count reduction is the more meaningful evidence.\n\nSelf-citation is present but justified; the algorithm builds directly on the authors' RQZ work. Overall, this is a solid paper that deserves a serious referee. The authors have done the work, compared against an independent implementation, and stated their caveats. I would send it out and ask for a more rigorous treatment of the dual swap case and, if possible, released code.","headline":"Solid, clearly explained new eigensolver algorithm; the unproven-duality gap in the Q-first swap is worth fixing but does not sink the paper.","tokens_in":720,"tokens_out":939,"would_cite":true,"duration_ms":68607,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F15","15A18"],"pacs":[],"model":"deepseek-v4-flash","headline":"The RQR algorithm is a pole-swapping alternative to the classic bulge-chasing QR algorithm for the standard eigenvalue problem, and the paper reports it is competitive: on average faster and with smaller backward errors.","keywords":["RQR algorithm","pole swapping","bulge chasing","QR algorithm","eigenvalue problem","core transformations","unitary Hessenberg matrices","backward stability"],"falsifier":"Compare the backward error of the two swap variants on matrices engineered so that one adjacent pole has slightly smaller modulus than the other; if the left-first variant ever produces a backward error or a subdiagonal bulge beyond what the reverse-order analysis predicts, the assumed duality fails.","tokens_in":10132,"feed_emoji":"🧮","tokens_out":7855,"duration_ms":65101,"temperature":0.7,"pith_summary":"The paper introduces RQR, a pole-swapping algorithm for computing the eigenvalues of a dense nonsymmetric matrix. It claims that RQR solves the standard eigenvalue problem by applying a pole-swapping sweep to the pencil $A - \\lambda U$, where $U$ stays a unitary upper Hessenberg matrix stored as core transformations, and that this approach is competitive with the classic bulge-chasing QR algorithm. In numerical tests on random Hessenberg matrices and on test matrices from standard collections, RQR was on average about 17 percent faster for dimensions below 75 and 29 percent faster above, with backward errors smaller by a factor of 1.5 to 2. If that holds, pole swapping is a viable alternative to bulge chasing for the standard eigenvalue problem, not only for generalized pencils.","feed_headline":"Pole swapping beats classic QR on dense eigenvalue tests","feed_subtitle":"The RQR algorithm runs about 17-29 percent faster, with 1.5-2 times smaller backward errors.","key_machinery":"The load-bearing machinery is the pole-swapping sweep on the Hessenberg pencil $A - \\lambda U$. The poles are the ratios $a_{j+1,j}/u_{j+1,j}$ of subdiagonal entries, and swapping adjacent poles is equivalent to interchanging adjacent eigenvalues of the pole pencil, done with two core transformations $Q_j$ and $Z_{j-1}$ built from a standard construction for interchanging adjacent eigenvalues. The algorithm uses two variants: when $|\\lambda_1| \\ge |\\lambda_2|$ it applies the right core first, and when $|\\lambda_1| < |\\lambda_2|$ it applies the left core first. $U$ is updated by turnovers so it remains exactly upper Hessenberg, while $A$ only picks up a roundoff-level bulge. This structure keeps the iterations cheap and the stored unitary factor stable.","core_discovery":"On the paper's own terms, the central discovery is that the pole-swapping idea, previously used for generalized pencils $A - \\lambda B$, can be specialized to the standard problem $A - \\lambda I$ while preserving efficiency and backward stability. The key is to keep the pencil $A - \\lambda U$ with $A$ upper Hessenberg and $U$ unitary upper Hessenberg; $U$ is stored compactly as a product of core transformations. RQR inserts a shift as a pole at the top, swaps it along the subdiagonal to the bottom by two types of moves, and inserts a finite pole at the bottom to accelerate convergence at the top. The paper reports that this single-shift RQR, compared with the standard QR kernel, consistently needs fewer iterations per eigenvalue, is on average faster, and yields smaller backward errors.","pith_inferences":["A natural test beyond the paper: matrices with tightly clustered eigenvalues, where the $|\\lambda_1|$ versus $|\\lambda_2|$ swap decision is sensitive, could reveal whether the left-first variant's assumed duality ever degrades backward stability.","The accuracy gap tracks the iteration-count gap, so the backward-error advantage may be mostly a side effect of fewer roundoff passes; a multishift RQR with equal iteration counts would probably show a smaller accuracy difference.","The same core-transformation storage could transfer to polynomial eigenvalue problems or to structured matrices, since only the Hessenberg-unitary pencil structure is used."],"forward_implications":["A single-shift RQR routine can replace the QR kernel for dense nonsymmetric eigenvalue problems in the small-to-medium range, with a typical speed advantage and comparable or better backward stability.","Because RQR needs fewer iterations per eigenvalue, roundoff accumulation is reduced; the observed 1.5 to 2 times smaller backward error follows directly from the shorter sweep.","The finite pole inserted at the bottom of each iteration accelerates convergence at the top of the pencil, a structural difference from bulge chasing that explains the lower iteration counts.","The missing multishift and aggressive-early-deflation machinery is the paper's stated next step before a fully fair comparison with production multishift QR is possible."],"supporting_citations":[{"why":"Supplies the backward-stability and roundoff analysis for the reverse-order pole swap that RQR builds on, and the paper assumes the other swap order is dual to it.","marker":"[9]"},{"why":"Introduced the RQZ pole-swapping algorithm for generalized eigenvalue problems, which RQR adapts to the standard problem.","marker":"[10]"},{"why":"Provides the basic procedure for swapping adjacent eigenvalues of the 2-by-2 subpencil used in each type II move.","marker":"[16]"},{"why":"The classic bulge-chasing QR algorithm that RQR is compared against.","marker":"[11]"},{"why":"The QZ algorithm for generalized pencils, the framework to which RQZ reduces and whose Hessenberg-triangular case informs the RQR design.","marker":"[14]"},{"why":"Supplies the core-chasing terminology, turnover operations, and storage conventions used to keep the unitary factor in Hessenberg form.","marker":"[1]"}],"fun_headline_variants":["RQR algorithm: pole-swapping beats classic QR","Pole-swapping RQR algorithm outpaces QR","RQR: a faster, more accurate QR alternative","RQR algorithm: faster and more accurate than QR"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument hinges on the assumption that computing the left core transformation before the right one in the swap is exactly as backward stable as the reverse order, even though the stability analysis is written out only for the reverse order.","fun_headline_variants_meta":{"raw":{"variants":["RQR algorithm: pole-swapping beats classic QR","Pole-swapping RQR algorithm outpaces QR","RQR: a faster, more accurate QR alternative","RQR algorithm: faster and more accurate than QR"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001061,"raw_usage":{"total_tokens":4363,"prompt_tokens":769,"completion_tokens":3594,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":385,"completion_tokens_details":{"reasoning_tokens":3531}},"tokens_in":385,"tokens_out":3594,"duration_ms":21317,"temperature":1.0,"reasoning_tokens":3531,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T11:50:31.766948+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compare the backward error of the two swap variants on matrices engineered so that one adjacent pole has slightly smaller modulus than the other; if the left-first variant ever produces a backward error or a subdiagonal bulge beyond what the reverse-order analysis predicts, the assumed duality fails.","supporting_citations":[{"cited_title":"Camps, T","cited_arxiv_id":null,"evidence_quote":"Supplies the backward-stability and roundoff analysis for the reverse-order pole swap that RQR builds on, and the paper assumes the other swap order is dual to it."},{"cited_title":"Camps, K","cited_arxiv_id":null,"evidence_quote":"Introduced the RQZ pole-swapping algorithm for generalized eigenvalue problems, which RQR adapts to the standard problem."},{"cited_title":"V an Dooren, A generalized eigenvalue approach for solving Riccati equa tions, SIAM J","cited_arxiv_id":null,"evidence_quote":"Provides the basic procedure for swapping adjacent eigenvalues of the 2-by-2 subpencil used in each type II move."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The classic bulge-chasing QR algorithm that RQR is compared against."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The QZ algorithm for generalized pencils, the framework to which RQZ reduces and whose Hessenberg-triangular case informs the RQR design."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the core-chasing terminology, turnover operations, and storage conventions used to keep the unitary factor in Hessenberg form."}],"review_version":1}