The RQR algorithm

Daan Camps; David S. Watkins; Raf Vandebril; Thomas Mach

REVIEW 2 major objections 5 minor 18 references

The RQR algorithm

T0 review · 2 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read 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.

desk verdict Solid, clearly explained new eigensolver algorithm; the unproven-duality gap in the Q-first swap is worth fixing but does not sink the paper. read the letter →

arxiv 2411.17671 v2 pith:ALE77ARG submitted 2024-11-26 math.NA cs.NA

Daan Camps , Thomas Mach , Raf Vandebril , David S. Watkins This is my paper · ORCID

classification math.NAcs.NA MSC 65F1515A18

keywords RQRalgorithmpoleswappingbulgechasingQReigenvalueproblemcoretransformationsunitaryHessenbergmatricesbackwardstability

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 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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

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.

Desk Editor's Note

read the 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.

The 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.

Two 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.

Self-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.

Referee Report

2 major / 5 minor

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.

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 (2)

[Section 2, case |λ1| < |λ2|] 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 5, Figure 5.1 and Table 5.1] 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.

minor comments (5)

[Abstract / Section 5] 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).
[Figure 5.1] 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 2, moves of type I] 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.
[Table 5.2] 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.
[References] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: RQR's competitive claim rests on independent LAPACK benchmarks; the flagged Q-first 'dual' gap is a stability assumption, not a circular reduction.

full rationale

The derivation chain is not circular. RQR is constructed from exact core-transformation identities (Section 2): the pole pencil's eigenvalues are the pole ratios by definition, and the two swap variants solve exactly the stated 2x2 pencil equations; neither step fits a parameter to the target conclusion. The central performance claim (Section 5) is tested against LAPACK's ZLAHQR, an independent external implementation, on random and Matrix Market matrices; no parameters are fitted to these results, so the measured speedup and smaller backward error are external evidence rather than a renamed prediction. Self-citations to [8], [9], and [10] supply the RQZ framework and prior error analysis, but the paper's own conclusion does not reduce to those citations: it is reproducible from the code and test set. The one explicitly incomplete passage is Section 2's assertion that the Q-first swap 'is dual' to the Z-first analysis in [9] 'and has the same numerical properties' although '[t]he analysis in [9] does not mention this case explicitly.' This is a genuine missing proof about backward stability of one branch, and it is a correctness risk if the duality fails; but it is not a circularity, because it does not make the algorithm's output equal to an input, fit a parameter, or rename a known result. Accordingly, the circularity score is 0.

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

RQR has no fitted free parameters and introduces no new entities. Its premises are the preservation of the A - λU pencil form, the transfer of the RQZ pole-swapping framework, the unproved stability of the Q-first swap by duality, and the smallness of roundoff fill-in. The external comparison against LAPACK's QR keeps the central claim non-circular.

assumptions (4)

domain assumption The pencil A - λU with A upper Hessenberg and U unitary upper Hessenberg is maintained by every move of types I and II.
Section 2 shows the transformations preserve this form; the whole algorithm and convergence discussion in Section 3 depends on it.
ad hoc to paper The Q-first swap variant is backward stable because it is dual to the Z-first variant.
Section 2, |λ1| < |λ2| case: the paper asserts the same numerical properties by duality although [9] does not analyze it.
domain assumption Roundoff-induced fill-in in the (j+1,j-1) entry of A is small enough to be ignored.
Invoked in both swap cases in Section 2; the paper cites [9] for the guarantee, and this underlies deflation in Section 3.
domain assumption The pole-swapping framework of RQZ [10] transfers to the standard pencil A - λI.
Section 2 builds on RQZ's swap machinery; the paper notes readers unfamiliar with [10] will need the literature.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The RQR algorithm." pith.science (2026). https://pith.science/paper/ALE77ARG

@misc{pith2026241117671,
  author       = {Pith},
  title        = {Pith review of: The RQR algorithm},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ALE77ARG}},
  note         = {Machine review of arXiv:2411.17671}
}

read the original abstract

Pole-swapping algorithms, generalizations of bulge-chasing algorithms, have been shown to be a viable alternative to the bulge-chasing QZ algorithm for solving the generalized eigenvalue problem for a matrix pencil A - {\lambda}B. It is natural to try to devise a pole-swapping algorithm that solves the standard eigenvalue problem for a single matrix A. This paper introduces such an algorithm and shows that it is competitive with Francis's bulge-chasing QR algorithm.

Figures

Figures reproduced from arXiv: 2411.17671 by the authors.

**Figure 5.1.** 10 15 23 34 51 76 114 171 256 384 577 865 1297 10−15 10−14 n = 75 Matrix Size Backward Error RQR QR hess(randn(n,n)) triu(i+j,-1) 10 15 23 34 51 76 114 171 256 384 577 865 1297 0.4 0.6 0.8 1 Avg. Accuracy Factor Matrix Size 10 15 23 34 51 76 114 171 256 384 577 865 1297 10−4 10−3 10−2 10−1 100 101 n = 75 Matrix Size Runtime t in s 10 15 23 34 51 76 114 171 256 384 577 865 1297 0.4 0.6 0.8 1 Matrix Size Avg. Speedup … view at source ↗

**Figure 5.** [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

[9]

Camps, T

D. Camps, T. Mach, R. V andebril, and D. S. W atkins , On pole-swapping algorithms for the eigenvalue problem , Electron. Trans. Numer. Anal., 52 (2020), pp. 480–508

work page 2020
[1]

J. L. Aurentz, T. Mach, L. Robol, R. V andebril, and D. S. W atki ns, Core-Chasing Algorithms for the Eigenvalue Problem , SIAM, Philadelphia, 2018

work page 2018
[2]

J. L. Aurentz, T. Mach, R. V andebril, and D. S. W atkins , eiscor – eigensolvers based on core transformations. https://github.com/eiscor/eiscor, 2014–2018

work page 2014
[3]

J. L. Aurentz, T. Mach, R. V andebril, and D. S. W atkins , Fast and backward stable computation of roots of polynomials , SIAM J. Matrix Anal. Appl., 36 (2015), pp. 942–973

work page 2015
[4]

J. L. Aurentz, T. Mach, R. V andebril, and D. S. W atkins , Fast and stable unitary QR algorithm, Electron. Trans. Numer. Anal., 44 (2015), pp. 327–341

work page 2015
[5]

R. F. Boisvert, R. Pozo, K. Remington, R. F. Barrett, and J. J. Dongarra, Matrix Mar- ket: a web resource for test matrix collections , Quality of Numerical Software: Assessment and Enhancement, (1997), pp. 125–137

work page 1997
[6]

Braman, R

K. Braman, R. Byers, and R. Matthias , The multishift QR algorithm, part I: Maintain- ing well focused shifts and level 3 performance , SIAM J. Matrix Anal. Appl., 23 (2001), pp. 929–947

work page 2001
[7]

Matrix Anal

, The multishift QR algorithm, part II: Aggressive early deﬂa tion, SIAM J. Matrix Anal. Appl., 23 (2001), pp. 948–973

work page 2001

Show all 18 references

[8]

Camps , Pole swapping methods for the eigenvalue problem: Rational QR algorithms , PhD thesis, KU Leuven, 2019

D. Camps , Pole swapping methods for the eigenvalue problem: Rational QR algorithms , PhD thesis, KU Leuven, 2019

2019
[10]

Camps, K

D. Camps, K. Meerbergen, and R. V andebril , A rational QZ method , SIAM J. Matrix Anal. Appl., 40 (2019), pp. 943–972

2019
[11]

J. G. F. Francis , The QR transformation, part II , Computer J., 4 (1961), pp. 332–345

1961
[12]

W. B. Gragg , The QR algorithm for unitary Hessenberg matrices , J. Comput. Appl. Math., 16 (1986), pp. 1–8

1986
[13]

Lang , Using level 3 BLAS in rotation-based algorithms , SIAM J

B. Lang , Using level 3 BLAS in rotation-based algorithms , SIAM J. Sci. Comput., 19 (1998), pp. 626–634

1998
[14]

C. B. Moler and G. W. Stew art , An algorithm for generalized matrix eigenvalue problems , SIAM J. Numer. Anal., 10 (1973), pp. 241–256

1973
[15]

Steel, D

T. Steel, D. Camps, K. Meerbergen, and R. V andebril , A multishift, multipole rational QZ method with aggressive early deﬂation , SIAM J. Sci. Comput., 42 (2021), pp. 753–774

2021
[16]

V an Dooren, A generalized eigenvalue approach for solving Riccati equa tions, SIAM J

P. V an Dooren, A generalized eigenvalue approach for solving Riccati equa tions, SIAM J. Sci. Stat. Comput., 2 (1981), pp. 121–135

1981
[17]

D. S. W atkins, The Matrix Eigenvalue Problem: GR and Krylov Subspace Metho ds, SIAM, Philadelphia, 2007

2007
[18]

, Francis’s algorithm, Amer. Math. Monthly, 118 (2011), pp. 387–403. 9 RQR QR n Time [s] BWE It/n n Time [s] BWE It/n 10 3.88e-05 1.30e-15 2.58 10 4.41e-05 1.93e-15 3.10 15 8.74e-05 1.61e-15 2.67 15 1.02e-04 2.42e-15 3.27 23 2.14e-04 2.00e-15 2.70 23 2.57e-04 3.03e-15 3.35 34 ...

2011

Pith tools

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

[1] [9]

Camps, T

D. Camps, T. Mach, R. V andebril, and D. S. W atkins , On pole-swapping algorithms for the eigenvalue problem , Electron. Trans. Numer. Anal., 52 (2020), pp. 480–508

work page 2020

[2] [1]

J. L. Aurentz, T. Mach, L. Robol, R. V andebril, and D. S. W atki ns, Core-Chasing Algorithms for the Eigenvalue Problem , SIAM, Philadelphia, 2018

work page 2018

[3] [2]

J. L. Aurentz, T. Mach, R. V andebril, and D. S. W atkins , eiscor – eigensolvers based on core transformations. https://github.com/eiscor/eiscor, 2014–2018

work page 2014

[4] [3]

J. L. Aurentz, T. Mach, R. V andebril, and D. S. W atkins , Fast and backward stable computation of roots of polynomials , SIAM J. Matrix Anal. Appl., 36 (2015), pp. 942–973

work page 2015

[5] [4]

J. L. Aurentz, T. Mach, R. V andebril, and D. S. W atkins , Fast and stable unitary QR algorithm, Electron. Trans. Numer. Anal., 44 (2015), pp. 327–341

work page 2015

[6] [5]

R. F. Boisvert, R. Pozo, K. Remington, R. F. Barrett, and J. J. Dongarra, Matrix Mar- ket: a web resource for test matrix collections , Quality of Numerical Software: Assessment and Enhancement, (1997), pp. 125–137

work page 1997

[7] [6]

Braman, R

K. Braman, R. Byers, and R. Matthias , The multishift QR algorithm, part I: Maintain- ing well focused shifts and level 3 performance , SIAM J. Matrix Anal. Appl., 23 (2001), pp. 929–947

work page 2001

[8] [7]

Matrix Anal

, The multishift QR algorithm, part II: Aggressive early deﬂa tion, SIAM J. Matrix Anal. Appl., 23 (2001), pp. 948–973

work page 2001