pith. sign in

arxiv: 2511.02598 · v2 · submitted 2025-11-04 · 🧮 math.NA · cs.NA

A Block-Shifted Cyclic Reduction Algorithm for Solving a Class of Quadratic Matrix Equations

Xu Li , Beatrice Meini This is my paper

Pith reviewed 2026-05-18 01:08 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords quadratic matrix equationscyclic reductionblock shift-and-deflatesingular value decompositionquasi-birth-death processesnumerical linear algebramatrix polynomials
0
0 comments X

The pith

The Block-Shifted CR algorithm extends cyclic reduction to quadratic matrix equations with multiple eigenvalues on the unit circle using SVD and block deflation.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a Block-Shifted Cyclic Reduction algorithm to solve quadratic matrix equations that arise in quasi-birth-death processes. Standard cyclic reduction may not converge if the matrix polynomial has more than one eigenvalue on the unit circle. The new method integrates singular value decomposition with block shift-and-deflate techniques to overcome this limitation. This extension allows the solver to handle a larger class of problems reliably. Numerical experiments illustrate the improved convergence and robustness of the approach.

Core claim

The Block-Shifted CR algorithm modifies the standard cyclic reduction iteration by using singular value decomposition to detect and deflate blocks corresponding to additional eigenvalues on the unit circle, thereby guaranteeing convergence to the minimal nonnegative solution for a broader family of quadratic matrix equations.

What carries the argument

The SVD-driven block shift-and-deflate operation embedded in the cyclic reduction iteration to neutralize the influence of multiple unit-circle eigenvalues.

Load-bearing premise

The SVD-based block shift-and-deflate procedure can be executed in a stable manner that leaves the set of solutions unchanged for every quadratic matrix equation with multiple unit-circle eigenvalues.

What would settle it

A concrete quadratic matrix equation possessing multiple eigenvalues on the unit circle for which the Block-Shifted CR iteration either diverges or returns an incorrect minimal nonnegative solution.

Figures

Figures reproduced from arXiv: 2511.02598 by Beatrice Meini, Xu Li.

Figure 1
Figure 1. Figure 1: Residual errors for the different versions of CR applied to Example 2 [PITH_FULL_IMAGE:figures/full_fig_p013_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: CPU time and number of iterations for the different versions of CR applied to Example 2 [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
read the original abstract

The cyclic reduction (CR) algorithm is an efficient method for solving quadratic matrix equations that arise in quasi-birth-death (QBD) stochastic processes. However, its convergence is not guaranteed when the associated matrix polynomial has more than one eigenvalue on the unit circle. To address this limitation, we introduce a novel iteration method, referred to as the Block-Shifted CR algorithm, that improves the CR algorithm by utilizing singular value decomposition (SVD) and block shift-and-deflate techniques. This new approach extends the applicability of existing solvers to a broader class of quadratic matrix equations. Numerical experiments demonstrate the effectiveness and robustness of the proposed method.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces a Block-Shifted Cyclic Reduction (CR) algorithm for quadratic matrix equations arising in quasi-birth-death processes. Standard CR fails to converge when the matrix polynomial has more than one eigenvalue on the unit circle; the new method augments CR with SVD-based block shift-and-deflate steps to extend applicability, and numerical experiments are asserted to demonstrate effectiveness and robustness.

Significance. If the SVD-driven deflation step can be shown to preserve the minimal nonnegative solution and to remain stable, the algorithm would meaningfully enlarge the set of quadratic matrix equations amenable to cyclic reduction, which is of practical interest in stochastic process modeling. The approach builds on established linear-algebra primitives without introducing free parameters or self-referential definitions.

major comments (2)
  1. [Algorithm description (likely §3)] The manuscript supplies no theorem, invariance argument, or perturbation analysis establishing that the SVD-based block shift-and-deflate operation leaves the original minimal nonnegative solution unchanged when multiple eigenvalues lie on the unit circle. This invariance is load-bearing for the central claim that the algorithm solves the intended quadratic matrix equation rather than a modified one.
  2. [Numerical experiments section] No convergence proof, residual bounds, or error analysis is provided for the modified iteration. The abstract's assertion that numerical experiments demonstrate effectiveness therefore rests on an unverified claim; the experiments themselves are not described with respect to test-matrix construction or spectrum properties.
minor comments (2)
  1. [Preliminaries / Algorithm] Notation for the block-shifted polynomial and the deflation operator should be introduced with explicit definitions before the algorithmic steps are presented.
  2. [Introduction] Standard references to the original cyclic reduction method and to existing shift-and-deflate techniques for matrix polynomials should be cited to clarify the precise novelty.

Simulated Author's Rebuttal

2 responses · 1 unresolved

Thank you for the opportunity to respond to the referee's report. We appreciate the referee's recognition of the potential significance of the Block-Shifted CR algorithm and the constructive feedback provided. We address the major comments in detail below, indicating the revisions we intend to make to the manuscript.

read point-by-point responses

  1. Referee: [Algorithm description (likely §3)] The manuscript supplies no theorem, invariance argument, or perturbation analysis establishing that the SVD-based block shift-and-deflate operation leaves the original minimal nonnegative solution unchanged when multiple eigenvalues lie on the unit circle. This invariance is load-bearing for the central claim that the algorithm solves the intended quadratic matrix equation rather than a modified one.

    Authors: We concur that establishing the invariance of the minimal nonnegative solution under the SVD-based block shift-and-deflate operation is crucial. In the revised manuscript, we will insert a dedicated lemma in the algorithm description section. This lemma will demonstrate that the deflation step, which targets the unit-circle eigenvalues via SVD, does not alter the minimal nonnegative solution by preserving the relevant invariant subspaces associated with the stable eigenvalues. We will also include a brief perturbation analysis to address numerical stability concerns. revision: yes

  2. Referee: [Numerical experiments section] No convergence proof, residual bounds, or error analysis is provided for the modified iteration. The abstract's assertion that numerical experiments demonstrate effectiveness therefore rests on an unverified claim; the experiments themselves are not described with respect to test-matrix construction or spectrum properties.

    Authors: We acknowledge that the current manuscript does not include a formal convergence proof or detailed error analysis for the Block-Shifted CR iteration. We will revise the numerical experiments section to provide comprehensive descriptions of the test matrix constructions, including how the spectra are controlled to have multiple unit-circle eigenvalues. We will also report residual norms and observed convergence behaviors to support the effectiveness claims. revision: partial

standing simulated objections not resolved
  • A complete convergence proof for the Block-Shifted CR algorithm

Circularity Check

0 steps flagged

No significant circularity; derivation relies on independent algorithmic extension

full rationale

The paper introduces the Block-Shifted CR algorithm as an extension of standard cyclic reduction using SVD-based block shift-and-deflate for quadratic matrix equations with multiple unit-circle eigenvalues. No load-bearing steps reduce by construction to fitted inputs, self-definitions, or self-citation chains; the method is presented as building on established linear-algebra primitives without renaming known results or smuggling ansatzes. The abstract and method description contain no equations or derivations that make the claimed convergence improvement tautological, leaving the central claim with independent content from the proposed techniques.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The approach rests on standard numerical linear algebra assumptions about the applicability of SVD and deflation; no new free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • domain assumption Singular value decomposition and block shift-and-deflate operations can be applied to move multiple unit-circle eigenvalues without destroying the solution or introducing instability.
    This premise is required for the new iteration to succeed on the targeted class of problems.

pith-pipeline@v0.9.0 · 5629 in / 1248 out tokens · 37466 ms · 2026-05-18T01:08:16.623655+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages

  1. [1]

    J. J. Sylvester, On Hamilton’s quadratic-equation and the general unilateral-equation in matrices, Phil. Mag. (5) 18 (1884) 454–458

    work page

  2. [2]

    Latouche, V

    G. Latouche, V. Ramaswami, Introduction to matrix analytic methods in stochastic modeling, volume 5 ofASA-SIAM Ser. Stat. Appl. Probab., Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM), 1999. doi:10.1137/1.9780898719734

    work page doi:10.1137/1.9780898719734 1999

  3. [3]

    D. A. Bini, G. Latouche, B. Meini, Numerical methods for structured Markov chains, Nu- mer. Math. Sci. Comput., Oxford: Oxford University Press, 2005. doi:10.1093/acprof:oso/ 9780198527688.001.0001

    work page doi:10.1093/acprof:oso/ 2005

  4. [4]

    Meini, On certain classes of nonlinear matrix equations: theory, applications, and numerical solution, Boll

    B. Meini, On certain classes of nonlinear matrix equations: theory, applications, and numerical solution, Boll. Unione Mat. Ital. 18 (2025) 293–309. doi:10.1007/s40574-024-00443-6

    work page doi:10.1007/s40574-024-00443-6 2025

  5. [5]

    Lancaster, L

    P. Lancaster, L. Rodman, Algebraic Riccati equations, Oxford: Clarendon Press, 1995

    work page 1995

  6. [6]

    Lancaster, Lambda-matrices and vibrating systems, volume 94 ofInt

    P. Lancaster, Lambda-matrices and vibrating systems, volume 94 ofInt. Ser. Monogr. Pure Appl. Math., Oxford: Pergamon Press, 1966

    work page 1966

  7. [7]

    J. E. j. Dennis, J. F. Traub, R. P. Weber, The algebraic theory of matrix polynomials, SIAM J. Numer. Anal. 13 (1976) 831–845. doi:10.1137/0713065

    work page doi:10.1137/0713065 1976

  8. [8]

    Tisseur, K

    F. Tisseur, K. Meerbergen, The quadratic eigenvalue problem, SIAM Rev. 43 (2001) 235–286. doi:10.1137/S0036144500381988

    work page doi:10.1137/s0036144500381988 2001

  9. [9]

    Guo, On a quadratic matrix equation associated with anM-matrix, IMA J

    C.-H. Guo, On a quadratic matrix equation associated with anM-matrix, IMA J. Numer. Anal. 23 (2003) 11–27. doi:10.1093/imanum/23.1.11

    work page doi:10.1093/imanum/23.1.11 2003

  10. [10]

    L. C. G. Rogers, Fluid models in queueing theory and Wiener-Hopf factorization of Markov chains, Ann. Appl. Probab. 4 (1994) 390–413. doi:10.1214/aoap/1177005065

    work page doi:10.1214/aoap/1177005065 1994

  11. [11]

    N. J. Higham, H.-M. Kim, Numerical analysis of a quadratic matrix equation, IMA J. Numer. Anal. 20 (2000) 499–519. doi:10.1093/imanum/20.4.499

    work page doi:10.1093/imanum/20.4.499 2000

  12. [12]

    G. H. Golub, C. F. Van Loan, Matrix computations, 4th ed., Baltimore, MD: The Johns Hopkins University Press, 2013

    work page 2013

  13. [13]

    N. J. Higham, H.-M. Kim, Solving a quadratic matrix equation by Newton’s method with exact line searches, SIAM J. Matrix Anal. Appl. 23 (2001) 303–316. doi:10.1137/S0895479899350976. 15

    work page doi:10.1137/s0895479899350976 2001

  14. [14]

    Bai, Y.-H

    Z.-Z. Bai, Y.-H. Gao, Modified Bernoulli iteration methods for quadratic matrix equation, J. Comput. Math. 25 (2007) 498–511

    work page 2007

  15. [15]

    Bai, A class of iteration methods based on the Moser formula for nonlinear equations in Markov chains, Linear Algebra Appl

    Z.-Z. Bai, A class of iteration methods based on the Moser formula for nonlinear equations in Markov chains, Linear Algebra Appl. 266 (1997) 219–241. doi:10.1016/S0024-3795(97)86522-6

    work page doi:10.1016/s0024-3795(97)86522-6 1997

  16. [16]

    Meini, New convergence results on functional iteration techniques for the numerical solution of M/G/1 type Markov chains, Numer

    B. Meini, New convergence results on functional iteration techniques for the numerical solution of M/G/1 type Markov chains, Numer. Math. 78 (1997) 39–58. doi:10.1007/s002110050303

    work page doi:10.1007/s002110050303 1997

  17. [17]

    Guo, On the numerical solution of a nonlinear matrix equation in Markov chains, Linear Algebra Appl

    C.-H. Guo, On the numerical solution of a nonlinear matrix equation in Markov chains, Linear Algebra Appl. 288 (1999) 175–186. doi:10.1016/S0024-3795(98)10190-8

    work page doi:10.1016/s0024-3795(98)10190-8 1999

  18. [18]

    Favati, B

    P. Favati, B. Meini, On functional iteration methods for solving nonlinear matrix equations arising in queueing problems, IMA J. Numer. Anal. 19 (1999) 39–49. doi:10.1093/imanum/19.1.39

    work page doi:10.1093/imanum/19.1.39 1999

  19. [19]

    D. A. Bini, G. Latouche, B. Meini, A family of fast fixed point iterations for M/G/1-type Markov chains, IMA J. Numer. Anal. 42 (2022) 1454–1477. doi:10.1093/imanum/drab009

    work page doi:10.1093/imanum/drab009 2022

  20. [20]

    B. L. Buzbee, G. H. Golub, C. W. Nielson, On direct methods for solving Poisson’s equations, SIAM J. Numer. Anal. 7 (1970) 627–656. doi:10.1137/0707049

    work page doi:10.1137/0707049 1970

  21. [21]

    R. W. Hockney, A fast direct solution of Poisson’s equation using Fourier analysis, J. Assoc. Comput. Mach. 12 (1965) 95–113. doi:10.1145/321250.321259

    work page doi:10.1145/321250.321259 1965

  22. [22]

    Meini, Nonlinear matrix equations and structured linear algebra, Linear Algebra Appl

    B. Meini, Nonlinear matrix equations and structured linear algebra, Linear Algebra Appl. 413 (2006) 440–457. doi:10.1016/j.laa.2005.06.011

    work page doi:10.1016/j.laa.2005.06.011 2006

  23. [23]

    D. A. Bini, B. Meini, The cyclic reduction algorithm: From Poisson equation to stochastic processes and beyond. In memoriam of Gene H. Golub, Numer. Algorithms 51 (2009) 23–60. doi:10.1007/s11075-008-9253-0

    work page doi:10.1007/s11075-008-9253-0 2009

  24. [24]

    D. A. Bini, B. Meini, S. Steffé, B. Van Houdt, Structured Markov chains solver: software tools, in: Proceeding from the 2006 Workshop on Tools for Solving Structured Markov Chains, SMCtools ’06, Association for Computing Machinery, New York, NY, USA, 2006, p. 14–es. doi:10.1145/ 1190366.1190379

    work page arXiv 2006

  25. [25]

    Latouche, V

    G. Latouche, V. Ramaswami, A logarithmic reduction algorithm for quasi-birth-death processes, J. Appl. Probab. 30 (1993) 650–674. doi:10.2307/3214773

    work page doi:10.2307/3214773 1993

  26. [26]

    D. A. Bini, G. Latouche, B. Meini, Solving matrix polynomial equations arising in queueing problems, Linear Algebra Appl. 340 (2002) 225–244. doi:10.1016/S0024-3795(01)00426-8

    work page doi:10.1016/s0024-3795(01)00426-8 2002

  27. [27]

    Huang, R.-C

    T.-M. Huang, R.-C. Li, W.-W. Lin, Structure-preserving doubling algorithms for nonlinear matrix equations, volume 14 ofFundam. Algorithms, Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM), 2018. doi:10.1137/1.9781611975369

    work page doi:10.1137/1.9781611975369 2018

  28. [28]

    Chiang, E

    C.-Y. Chiang, E. K.-W. Chu, C.-H. Guo, T.-M. Huang, W.-W. Lin, S.-F. Xu, Convergence analysis of the doubling algorithm for several nonlinear matrix equations in the critical case, SIAM J. Matrix Anal. Appl. 31 (2009) 227–247. doi:10.1137/080717304

    work page doi:10.1137/080717304 2009

  29. [29]

    Guo, Convergence analysis of the Latouche–Ramaswami algorithm for null recurrent quasi-birth-death processes, SIAM J

    C.-H. Guo, Convergence analysis of the Latouche–Ramaswami algorithm for null recurrent quasi-birth-death processes, SIAM J. Matrix Anal. Appl. 23 (2002) 744–760. doi:10.1137/ S0895479800381872

    work page 2002

  30. [30]

    C. He, B. Meini, N. H. Rhee, A shifted cyclic reduction algorithm for quasi-birth-death problems, SIAM J. Matrix Anal. Appl. 23 (2001) 673–691. doi:10.1137/S0895479800371955

    work page doi:10.1137/s0895479800371955 2001

  31. [31]

    Guo, Comments on a shifted cyclic reduction algorithm for quasi-birth-death problems, SIAM J

    C.-H. Guo, Comments on a shifted cyclic reduction algorithm for quasi-birth-death problems, SIAM J. Matrix Anal. Appl. 24 (2003) 1161–1166. doi:10.1137/S0895479802407901

    work page doi:10.1137/s0895479802407901 2003

  32. [32]

    shift-and-deflate

    B. Meini, A “shift-and-deflate” technique for quadratic matrix polynomials, Linear Algebra Appl. 438 (2013) 1946–1961. doi:10.1016/j.laa.2011.11.037. 16

    work page doi:10.1016/j.laa.2011.11.037 2013

  33. [33]

    D. A. Bini, B. Meini, Generalization of the Brauer theorem to matrix polynomials and matrix Laurent series, in: Large truncated Toeplitz matrices, Toeplitz operators, and related topics. The Albrecht Böttcher anniversary volume, Basel: Birkhäuser/Springer, 2017, pp. 155–178. doi:10. 1007/978-3-319-49182-0_10

    work page 2017

  34. [34]

    D. A. Bini, G. Latouche, B. Meini, Shift techniques for quasi-birth and death processes: canonical factorizations and matrix equations, Appl. Numer. Math. 116 (2017) 24–36. doi:10.1016/j. apnum.2016.09.001

    work page doi:10.1016/j 2017

  35. [35]

    H. R. Gail, S. L. Hantler, B. A. Taylor, Spectral analysis ofM/G/1andG/M/1type Markov chains, Adv. in Appl. Probab. 28 (1996) 114–165. doi:10.2307/1427915. 17

    work page doi:10.2307/1427915 1996