pith. sign in

arxiv: 2604.23208 · v1 · submitted 2026-04-25 · 🧮 math.NA · cs.NA· cs.SY· eess.SY

A Low-rank ADI Algorithm for Solving Large-scale Non-symmetric Algebraic Riccati Equations

Umair Zulfiqar This is my paper

Pith reviewed 2026-05-08 07:39 UTC · model grok-4.3

classification 🧮 math.NA cs.NAcs.SYeess.SY
keywords low-rank ADInon-symmetric algebraic Riccati equationslarge-scale matrix equationsautomatic shift generationsubspace accelerationnumerical linear algebracontrol theory
0
0 comments X

The pith

A low-rank ADI algorithm solves large-scale non-symmetric algebraic Riccati equations autonomously after initial shifts.

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

This paper develops a low-rank alternating direction implicit (ADI) algorithm for large-scale nonsymmetric continuous-time algebraic Riccati equations that admit low-rank solutions. It generalizes existing low-rank ADI methods for Lyapunov equations, Sylvester equations, and symmetric Riccati equations, which appear as special cases. The method includes an automatic shift generation procedure based on a subspace-accelerated projection approach that produces effective shifts for later iterations without further user input. Numerical experiments on benchmark problems of matrix order one million show that the algorithm computes the solutions efficiently and accurately once started with arbitrary initial shifts.

Core claim

The central claim is that a low-rank ADI iteration, combined with subspace-accelerated projection for shift selection, computes low-rank solutions to large-scale NAREs and runs autonomously after arbitrary initialization, with prior low-rank ADI solvers for related equations recovered as special cases.

What carries the argument

Low-rank ADI iteration on factored solution matrices, accelerated by a subspace projection method that selects the next iteration shifts automatically from the current approximate solution subspace.

If this is right

  • All prior low-rank ADI solvers for Lyapunov, Sylvester, and symmetric Riccati equations become direct instances of the new general method.
  • Memory and arithmetic costs remain linear in the problem dimension when the solution rank stays small, enabling solution of systems with one million unknowns.
  • Once arbitrary initial shifts are supplied, the solver requires no further tuning, removing a common practical barrier for large problems.
  • Benchmark results on order-10^6 matrices confirm that the computed factors satisfy the equation to high accuracy in modest run times.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same automatic shift mechanism could be tested on discrete-time Riccati equations or other nonlinear matrix equations that preserve low-rank structure.
  • Coupling the projection step with additional subspace expansion techniques might extend the method to problems where the solution rank grows slowly during iteration.
  • Application to NAREs arising from discretized partial differential equations would test whether the low-rank assumption holds in concrete engineering models.

Load-bearing premise

The target equations must admit low-rank solutions, and the subspace-accelerated projection must reliably produce useful shifts without manual intervention after the first step.

What would settle it

A large-scale NARE known to possess a low-rank solution on which the algorithm diverges or loses accuracy despite the automatic shift procedure would falsify the claim.

Figures

Figures reproduced from arXiv: 2604.23208 by Umair Zulfiqar.

Figure 1
Figure 1. Figure 1: Normalized residual for X 4. Conclusion A low-rank ADI algorithm for solving large-scale NAREs is presented. The mathematical properties and residual expression for tracking the quality of approximation in large-scale setting are also discussed. Two implementations of the algorithm are presented. One uses the SMW formula while the other uses the low-rank ADI algorithm for Lyapunov equations as a base algor… view at source ↗
read the original abstract

This paper considers large-scale nonsymmetric continuous-time algebraic Riccati equations (NAREs) that admit low-rank solutions. Low-rank alternating direction implicit (ADI) methods have proven to be an efficient approach for solving several matrix equations, including Lyapunov equations, Sylvester equations, and symmetric Riccati equations. Although a low-rank algorithm for the Sylvester equation has been used as an inner loop in computing low-rank solutions of NAREs, no low-rank ADI algorithm currently exists for NAREs themselves. This paper fills this gap by developing a low-rank ADI algorithm for large-scale NAREs that admit a low-rank solution. Since Lyapunov equations, Sylvester equations, and symmetric Riccati equations are special cases of the NARE, the existing low-rank ADI methods in the literature are special cases of the more general low-rank ADI method proposed here. An automatic and computationally efficient method for shift generation is also discussed, and a subspace-accelerated projection approach is presented to generate shifts for subsequent iterations without user intervention. Once initialized with arbitrary shifts, the proposed algorithm solves large-scale NAREs autonomously, generating its own shifts. Numerical results are presented using benchmark example of order $10^6$, demonstrating the computational efficiency and accuracy of the proposed algorithm.

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 / 1 minor

Summary. The paper develops a low-rank ADI algorithm for large-scale non-symmetric algebraic Riccati equations (NAREs) that admit low-rank solutions. It generalizes existing low-rank ADI schemes for Lyapunov, Sylvester, and symmetric Riccati equations as special cases, and introduces an autonomous shift-generation procedure based on subspace-accelerated projection that requires only arbitrary initial shifts. Numerical results on a single benchmark of order 10^6 are reported to illustrate computational efficiency and accuracy.

Significance. If the derivation and shift generator are correct, the work would fill a documented gap in scalable solvers for NAREs arising in control applications. The explicit embedding of prior methods as special cases and the emphasis on low-rank structure plus autonomy are clear strengths. The reported performance on a 10^6-order problem supports practical relevance, though the significance hinges on the missing theoretical backing.

major comments (2)
  1. [Algorithm description] The central claim rests on the correctness of the low-rank ADI iteration for the non-symmetric case, yet the manuscript provides neither the explicit low-rank update formulas nor a derivation showing how the iteration is obtained from the symmetric Riccati case (see the algorithm description section). Without these, it is impossible to verify that the low-rank property is preserved and that the method reduces correctly to the known special cases.
  2. [Shift generation] The subspace-accelerated projection method is asserted to generate effective shifts autonomously after arbitrary initialization, but no convergence analysis, residual bound, or spectral assumption is supplied to support this claim (see the shift-generation section). This is load-bearing for the autonomy and reliability assertions.
minor comments (1)
  1. [Numerical results] The numerical-results section reports performance on a 10^6-order benchmark but omits the precise definition of the test NARE (matrices A, B, C, R, Q), the stopping criterion, and the error measure used; these details are needed for reproducibility.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address the two major comments point by point below and will revise the paper to improve clarity and completeness.

read point-by-point responses

  1. Referee: [Algorithm description] The central claim rests on the correctness of the low-rank ADI iteration for the non-symmetric case, yet the manuscript provides neither the explicit low-rank update formulas nor a derivation showing how the iteration is obtained from the symmetric Riccati case (see the algorithm description section). Without these, it is impossible to verify that the low-rank property is preserved and that the method reduces correctly to the known special cases.

    Authors: We agree that the explicit low-rank update formulas and a derivation from the symmetric Riccati case are necessary for full verification. Although the manuscript outlines the generalization, we will expand the algorithm description section in the revision to include the detailed low-rank update formulas for the NARE and a step-by-step derivation showing preservation of the low-rank structure and correct reduction to the Lyapunov, Sylvester, and symmetric Riccati cases. revision: yes

  2. Referee: [Shift generation] The subspace-accelerated projection method is asserted to generate effective shifts autonomously after arbitrary initialization, but no convergence analysis, residual bound, or spectral assumption is supplied to support this claim (see the shift-generation section). This is load-bearing for the autonomy and reliability assertions.

    Authors: We acknowledge that the absence of a convergence analysis or residual bounds limits the theoretical support for the autonomous shift generation. The manuscript presents the subspace-accelerated projection method as a practical heuristic that operates with arbitrary initial shifts and is validated numerically on the large-scale benchmark. In the revision we will add a discussion of the underlying spectral assumptions and any available heuristic bounds in the shift-generation section, while clarifying that a full convergence proof lies beyond the current scope. revision: partial

Circularity Check

0 steps flagged

No significant circularity; derivation is a direct constructive extension

full rationale

The paper constructs a low-rank ADI iteration for NAREs by embedding the known low-rank ADI schemes for Lyapunov, Sylvester, and symmetric Riccati equations as special cases, then extending the iteration and shift logic to the nonsymmetric setting. The autonomous shift generator is based on an independent subspace-accelerated projection approach that does not reduce to the target solution by construction or fitting. No self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations appear in the derivation chain. Numerical results on benchmarks serve only for validation of the constructed algorithm.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The contribution is primarily algorithmic. It rests on the domain assumption that the NARE admits a low-rank solution and that ADI iterations converge under the generated shifts. No new physical entities are introduced. Initial shifts are arbitrary (not fitted). Since only the abstract is available, any internal parameters in the shift-generation procedure cannot be audited.

free parameters (1)
  • initial shifts
    Arbitrary initial shifts are supplied by the user; the algorithm then generates subsequent shifts autonomously via subspace projection.
axioms (1)
  • domain assumption The NARE admits a low-rank solution
    The algorithm is developed specifically for NAREs that admit low-rank solutions, as stated in the abstract.

pith-pipeline@v0.9.0 · 5534 in / 1554 out tokens · 97295 ms · 2026-05-08T07:39:24.243390+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages · 1 internal anchor

  1. [1]

    Freiling, A survey of nonsymmetric Riccati equations, Linear Algebra and Its Applications 351 (2002) 243–270

    G. Freiling, A survey of nonsymmetric Riccati equations, Linear Algebra and Its Applications 351 (2002) 243–270

    work page 2002

  2. [2]

    Abou-Kandil, G

    H. Abou-Kandil, G. Freiling, V. Ionescu, G. Jank, Non-symmetric Riccati theory and applications, in: Matrix Riccati Equations in Control and Systems Theory, Springer, 2003, pp. 495–525

    work page 2003

  3. [3]

    D. A. Bini, B. Iannazzo, F. Poloni, A fast Newton’s method for a nonsymmetric algebraic Riccati equation, SIAM Journal on Matrix Analysis and Applications 30 (1) (2008) 276–290

    work page 2008

  4. [4]

    T. Li, E. K.-W. Chu, Y.-C. Kuo, W.-W. Lin, Solving large-scale nonsymmetric algebraic Riccati equa- tions by doubling, SIAM Journal on Matrix Analysis and Applications 34 (3) (2013) 1129–1147

    work page 2013

  5. [5]

    Benner, P

    P. Benner, P. Kuerschner, J. Saak, Low-rank Newton-ADI methods for large nonsymmetric algebraic Riccati equations, Journal of the Franklin Institute 353 (5) (2016) 1147–1167

    work page 2016

  6. [6]

    P. C.-Y. Weng, Solving large-scale nonsymmetric algebraic Riccati equations from two-dimensional transport models by doubling, Journal of Computational and Applied Mathematics 391 (2021) 113447

    work page 2021

  7. [7]

    G. H. Golub, C. F. Van Loan, Matrix computations, JHU press, 2013

    work page 2013

  8. [8]

    Benner, P

    P. Benner, P. Kürschner, Computing real low-rank solutions of Sylvester equations by the factored ADI method, Computers & Mathematics with Applications 67 (9) (2014) 1656–1672

    work page 2014

  9. [9]

    K.Gallivan, A.Vandendorpe, P.VanDooren, Sylvesterequationsandprojection-basedmodelreduction, Journal of Computational and Applied Mathematics 162 (1) (2004) 213–229

    work page 2004

  10. [10]

    Wolf,H 2 pseudo-optimal model order reduction, Ph.D

    T. Wolf,H 2 pseudo-optimal model order reduction, Ph.D. thesis, Technische Universität München (2014)

    work page 2014

  11. [11]

    H. K. Panzer, Model order reduction by Krylov subspace methods with global error bounds and auto- matic choice of parameters, Ph.D. thesis, Technische Universität München (2014)

    work page 2014

  12. [12]

    Astolfi, Model reduction by moment matching for linear and nonlinear systems, IEEE Transactions on Automatic Control 55 (10) (2010) 2321–2336

    A. Astolfi, Model reduction by moment matching for linear and nonlinear systems, IEEE Transactions on Automatic Control 55 (10) (2010) 2321–2336

    work page 2010

  13. [13]

    Benner, P

    P. Benner, P. Kürschner, J. Saak, A reformulated low-rank ADI iteration with explicit residual factors, PAMM 13 (1) (2013) 585–586

    work page 2013

  14. [14]

    Zulfiqar, Z.-Y

    U. Zulfiqar, Z.-Y. Huang, Q.-Y. Song, Z.-Y. Gao, A unified low-rank ADI framework with shared linear solves for simultaneously solving multiple Lyapunov, Sylvester, and Riccati equations, arXiv preprint arXiv:2512.04676 (2025)

    work page arXiv 2025

  15. [15]

    T.Wolf, H.K.Panzer, TheADIiterationforLyapunovequationsimplicitlyperformsH 2 pseudo-optimal model order reduction, International Journal of Control 89 (3) (2016) 481–493

    work page 2016

  16. [16]

    $LDL^\top$ Factorization-based Generalized Low-rank ADI Algorithm for Solving Large-scale Algebraic Riccati Equations

    U. Zulfiqar,LDL ⊤ factorization-based generalized low-rank ADI algorithm for solving large-scale alge- braic Riccati equations, arXiv preprint arXiv:2604.06556 (2026)

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  17. [17]

    Benner, P

    P. Benner, P. Kürschner, J. Saak, Efficient handling of complex shift parameters in the low-rank Cholesky factor ADI method, Numerical Algorithms 62 (2) (2013) 225–251

    work page 2013

  18. [18]

    Benner, R.-C

    P. Benner, R.-C. Li, N. Truhar, On the ADI method for Sylvester equations, Journal of Computational and Applied Mathematics 233 (4) (2009) 1035–1045

    work page 2009

  19. [19]

    Benner, Z

    P. Benner, Z. Bujanović, P. Kürschner, J. Saak, RADI: A low-rank ADI-type algorithm for large scale algebraic Riccati equations, Numerische Mathematik 138 (2) (2018) 301–330. 36

    work page 2018

  20. [20]

    Rommes, Methods for eigenvalue problems with applications in model order reduction, Ph.D

    J. Rommes, Methods for eigenvalue problems with applications in model order reduction, Ph.D. thesis, Utrecht University (2007)

    work page 2007

  21. [21]

    Saad, Numerical methods for large eigenvalue problems: Revised edition, SIAM, 2011

    Y. Saad, Numerical methods for large eigenvalue problems: Revised edition, SIAM, 2011

    work page 2011

  22. [22]

    Rommes, N

    J. Rommes, N. Martins, Efficient computation of multivariable transfer function dominant poles using subspace acceleration, IEEE Transactions on Power Systems 21 (4) (2006) 1471–1483

    work page 2006

  23. [23]

    Rommes, G

    J. Rommes, G. L. Sleijpen, Convergence of the dominant pole algorithm and Rayleigh quotient iteration, SIAM Journal on Matrix Analysis and Applications 30 (1) (2008) 346–363

    work page 2008

  24. [24]

    Martins, L

    N. Martins, L. T. Lima, H. J. Pinto, Computing dominant poles of power system transfer functions, IEEE Transactions on Power Systems 11 (1) (1996) 162–170

    work page 1996

  25. [25]

    E.Mengi, Large-scaleestimationofdominantpolesofatransferfunctionbyaninterpolatoryframework, SIAM Journal on Scientific Computing 44 (4) (2022) A2412–A2438

    work page 2022

  26. [26]

    B. Anić, C. Beattie, S. Gugercin, A. C. Antoulas, Interpolatory weighted-H2 model reduction, Auto- matica 49 (5) (2013) 1275–1280

    work page 2013

  27. [27]

    Breiten, C

    T. Breiten, C. Beattie, S. Gugercin, Near-optimal frequency-weighted interpolatory model reduction, Systems & Control Letters 78 (2015) 8–18

    work page 2015

  28. [28]

    Benner, J

    P. Benner, J. Saak, A semi-discretized heat transfer model for optimal cooling of steel profiles, in: Di- mension Reduction of Large-Scale Systems: Proceedings of a Workshop held in Oberwolfach, Germany, October 19–25, 2003, Springer, 2005, pp. 353–356

    work page 2003

  29. [29]

    A low-rank ADI algorithm for solving large-scale non-symmetric algebraic Riccati equations

    U. Zulfiqar, MATLAB codes for “A low-rank ADI algorithm for solving large-scale non-symmetric algebraic Riccati equations”, https://doi.org/10.5281/zenodo.19753158 (2026). URLhttps://doi.org/10.5281/zenodo.19753158 37

    work page doi:10.5281/zenodo.19753158 2026