pith. sign in

arxiv: 2502.09165 · v4 · pith:L55ZXH4Knew · submitted 2025-02-13 · 🧮 math.NA · cs.NA

Generalizing Reduced Rank Extrapolation to Low-Rank Matrix Sequences

Pascal den Boef , Patrick K\"urschner , Xiaobo Liu , Jos Maubach , Jens Saak , Wil Schilders , Jonas Schulze , Nathan van de Wouw This is my paper

Pith reviewed 2026-05-23 03:35 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords reduced rank extrapolationlow-rank matricesfixed-point iterationLyapunov equationRiccati equationacceleration methodsmatrix equationsnumerical linear algebra
0
0 comments X

The pith

Reduced rank extrapolation extends to sequences of low-rank matrices and to fixed-point mappings that change each step.

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

The paper develops two extensions of reduced rank extrapolation so that the method can accelerate iterative solvers that produce low-rank matrix iterates. The first extension shows how to compute the extrapolation directly on low-rank matrix sequences without expanding them to full matrices. The second extension derives an RRE variant that works when the underlying fixed-point mapping itself varies from one iteration to the next. These changes make the acceleration technique applicable to large-scale matrix equations such as the Lyapunov and Riccati equations that arise in control and stability analysis. A reader would care because the low-rank structure keeps storage and arithmetic costs manageable while the changing-mapping version removes a previous restriction on the iteration process.

Core claim

We propose two novel generalizations of RRE. First, we show how to effectively compute RRE for sequences of low-rank matrices. Second, we derive a formulation of RRE that is suitable for fixed-point processes for which the mapping function changes each iteration. We demonstrate the potential of the methods on several numerical examples involving the iterative solution of large-scale Lyapunov and Riccati matrix equations.

What carries the argument

Generalized reduced-rank extrapolation formulas that operate directly on low-rank matrix factors and accommodate iteration-dependent mappings.

If this is right

  • Iterative solvers for large Lyapunov and Riccati equations can be accelerated while preserving the low-rank representation of each iterate.
  • The same low-rank RRE formulas remain valid when the fixed-point mapping changes at every step.
  • Numerical experiments on matrix equations confirm that the generalizations retain the acceleration property of classical RRE.
  • Storage and arithmetic costs stay proportional to the rank rather than the full matrix dimension.

Where Pith is reading between the lines

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

  • The approach could be tested on other matrix equations whose iterates naturally stay low-rank, such as certain Sylvester or Stein equations.
  • If the low-rank assumption holds only approximately, one could examine how rank truncation errors propagate through the extrapolated steps.
  • The variable-mapping formulation might apply to outer iterations that alternate between different equation types.

Load-bearing premise

The iterates remain low-rank throughout the process and the fixed-point mapping, even when it changes, still produces a sequence whose acceleration can be captured by the same low-rank extrapolation formulas.

What would settle it

A concrete low-rank matrix sequence generated by a changing mapping for which the proposed RRE formulas produce iterates whose residual or error does not decrease faster than the original unaccelerated sequence.

Figures

Figures reproduced from arXiv: 2502.09165 by Jens Saak, Jonas Schulze, Jos Maubach, Nathan van de Wouw, Pascal den Boef, Patrick K\"urschner, Wil Schilders, Xiaobo Liu.

Figure 3
Figure 3. Figure 3 [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 3
Figure 3. Figure 3 [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 3
Figure 3. Figure 3 [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
Figure 4
Figure 4. Figure 4 [PITH_FULL_IMAGE:figures/full_fig_p018_4.png] view at source ↗
Figure 4
Figure 4. Figure 4 [PITH_FULL_IMAGE:figures/full_fig_p019_4.png] view at source ↗
Figure 4
Figure 4. Figure 4 [PITH_FULL_IMAGE:figures/full_fig_p020_4.png] view at source ↗
Figure 4
Figure 4. Figure 4 [PITH_FULL_IMAGE:figures/full_fig_p021_4.png] view at source ↗
Figure 4
Figure 4. Figure 4 [PITH_FULL_IMAGE:figures/full_fig_p022_4.png] view at source ↗
read the original abstract

Reduced rank extrapolation (RRE) is an acceleration method typically used to accelerate the iterative solution of nonlinear systems of equations using a fixed-point process. In this context, the iterates are vectors generated from a fixed-point mapping function. However, when considering the iterative solution of large-scale matrix equations, the iterates are low-rank matrices generated from a fixed-point process for which, generally, the mapping function changes in each iteration. To enable acceleration of the iterative solution for these problems, we propose two novel generalizations of RRE. First, we show how to effectively compute RRE for sequences of low-rank matrices. Second, we derive a formulation of RRE that is suitable for fixed-point processes for which the mapping function changes each iteration. We demonstrate the potential of the methods on several numerical examples involving the iterative solution of large-scale Lyapunov and Riccati matrix equations.

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

0 major / 2 minor

Summary. The paper proposes two generalizations of reduced rank extrapolation (RRE) for accelerating fixed-point iterations that produce sequences of low-rank matrices, specifically when the mapping function changes at each step. The first generalization enables direct application of RRE to low-rank matrix sequences; the second derives an adapted RRE formulation for varying mappings. Effectiveness is illustrated through numerical experiments on the iterative solution of large-scale Lyapunov and Riccati equations.

Significance. If the generalizations perform as described in the numerical tests, the contribution would be useful for accelerating matrix-equation solvers that arise in control and model reduction. The empirical demonstrations on standard benchmark problems constitute a concrete strength of the work.

minor comments (2)
  1. The description of how the low-rank structure is maintained (or recovered) after each extrapolation step should be expanded for reproducibility, particularly in the first generalization.
  2. Notation for the changing mapping function could be clarified to distinguish it from the standard fixed-map case.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript, recognition of its potential utility in control and model reduction applications, and recommendation for minor revision. No major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper presents an algorithmic proposal for generalizing Reduced Rank Extrapolation (RRE) to sequences of low-rank matrices and to fixed-point iterations with iteration-dependent mappings. The central contributions are explicit computational reformulations and extensions of the existing RRE procedure, demonstrated via numerical examples on Lyapunov and Riccati equations. No parameter is fitted to a data subset and then relabeled as a prediction, no quantity is defined in terms of itself, and no load-bearing step reduces to a self-citation or imported uniqueness result. The derivation chain therefore remains self-contained and independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract supplies no explicit free parameters, axioms, or invented entities; all technical content is deferred to the unavailable full text.

pith-pipeline@v0.9.0 · 5702 in / 1078 out tokens · 18593 ms · 2026-05-23T03:35:48.364518+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

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

  1. [1]

    Alexander C. Aitken. On Bernoulli’s numerical solution of algebraic equations. Proceedings of the Royal Society of Edinburgh , 46:289–305, 1927. doi:10.1017/S0370164600022070

    work page doi:10.1017/s0370164600022070 1927

  2. [2]

    Conjugate gradient type methods for unsymmetric and inconsistent systems of linear equations

    Owe Axelsson. Conjugate gradient type methods for unsymmetric and inconsistent systems of linear equations. Linear Algebra Appl., 29:1–16, 1980. doi:10.1016/0024-3795(80)90226-8

    work page doi:10.1016/0024-3795(80)90226-8 1980

  3. [3]

    On the solution of large-scale algebraic Riccati equa- tions by using low-dimensional invariant subspaces

    Peter Benner and Zvonimir Bujanovi´ c. On the solution of large-scale algebraic Riccati equa- tions by using low-dimensional invariant subspaces. Linear Algebra Appl., 488:430–459, 2016. doi:10.1016/j.laa.2015.09.027

    work page doi:10.1016/j.laa.2015.09.027 2016

  4. [4]

    RADI: a low-rank ADI-type algorithm for large scale algebraic Riccati equations

    Peter Benner, Zvonimir Bujanovi´ c, Patrick K¨ urschner, and Jens Saak. RADI: a low-rank ADI-type algorithm for large scale algebraic Riccati equations. Numer. Math., 138:301–330,

    work page

  5. [5]

    doi:10.1007/s00211-017-0907-5

    work page doi:10.1007/s00211-017-0907-5

  6. [6]

    A numerical compar- ison of different solvers for large-scale, continuous-time algebraic Riccati equations and LQR problems

    Peter Benner, Zvonimir Bujanovi´ c, Patrick K¨ urschner, and Jens Saak. A numerical compar- ison of different solvers for large-scale, continuous-time algebraic Riccati equations and LQR problems. SIAM J. Sci. Comput. , 42(2):A957–A996, 2020. doi:10.1137/18M1220960

    work page doi:10.1137/18m1220960 2020

  7. [7]

    Self-generating and efficient shift parame- ters in ADI methods for large Lyapunov and Sylvester equations

    Peter Benner, Patrick K¨ urschner, and Jens Saak. Self-generating and efficient shift parame- ters in ADI methods for large Lyapunov and Sylvester equations. Electron. Trans. Numer. Anal., 43:142–162, 2014. URL: http://etna.mcs.kent.edu/volumes/2011-2020/vol43/ abstract.php?vol=43&pages=142-162

    work page 2014

  8. [8]

    An improved numerical method for balanced truncation for symmetric second-order systems

    Peter Benner, Patrick K¨ urschner, and Jens Saak. An improved numerical method for balanced truncation for symmetric second-order systems. Mathematical and Computer Modelling of Dynamical Systems, 19(6):593–615, 2013. doi:10.1080/13873954.2013.794363

    work page doi:10.1080/13873954.2013.794363 2013

  9. [9]

    Peter Benner, Jing-Rebecca Li, and Thilo Penzl. Numerical solution of large-scale Lyapunov equations, Riccati equations, and linear-quadratic optimal control problems.Numerical Linear Algebra with Applications, 15(9):755–777, 2008. doi:10.1002/nla.622. Preprint. 2025-12-11 29

    work page doi:10.1002/nla.622 2008

  10. [10]

    Linear-Quadratic Regulator Design for Optimal Cooling of Steel Profiles

    Peter Benner and Jens Saak. Linear-Quadratic Regulator Design for Optimal Cooling of Steel Profiles. Technical Report SFB393/05-05, Sonderforschungsbereich 393 Parallele Nu- merische Simulation f¨ ur Physik und Kontinuumsmechanik, TU Chemnitz, D-09107 Chemnitz (Germany), 2005. URL: http://nbn-resolving.de/urn:nbn:de:swb:ch1-200601597

    work page 2005

  11. [11]

    Matrix analysis , volume 169 of Graduate Texts in Mathematics

    Rajendra Bhatia. Matrix analysis , volume 169 of Graduate Texts in Mathematics . Springer Science & Business Media, New York, NY, 2013. doi:10.1007/978-1-4612-0653-8

    work page doi:10.1007/978-1-4612-0653-8 2013

  12. [12]

    Rajendra Bhatia and John A. R. Holbrook. Unitary invariance and spectral variation. Linear Algebra Appl., 95:43–68, 1987. doi:10.1016/0024-3795(87)90026-7

    work page doi:10.1016/0024-3795(87)90026-7 1987

  13. [13]

    D. A. Bini, B. Iannazzo, and B. Meini. Numerical solution of algebraic Riccati equations , volume 9 of Fundamentals of Algorithms . SIAM Publications, Philadelphia, 2012. doi: 10.1137/1.9781611972092

    work page doi:10.1137/1.9781611972092 2012

  14. [14]

    R. P. Eddy. Extrapolating to the limit of a vector sequence. In Information linkage between applied mathematics and industry , pages 387–396. Academic Press, Cambridge, MA, 1979. doi:10.1016/B978-0-12-734250-4.50028-X

    work page doi:10.1016/b978-0-12-734250-4.50028-x 1979

  15. [15]

    Eisenstat, Howard C

    Stanley C. Eisenstat, Howard C. Elman, and Martin H. Schultz. Variational iterative methods for nonsymmetric systems of linear equations. SIAM J. Numer. Anal. , 20(2):345–357, 1983. doi:10.1137/0720023

    work page doi:10.1137/0720023 1983

  16. [16]

    Vector extrapolation applied to algebraic Riccati equa- tions arising in transport theory

    Rola El-Moallem and Hassane Sadok. Vector extrapolation applied to algebraic Riccati equa- tions arising in transport theory. Electron. Trans. Numer. Anal. , 40:489–506, 2013. URL: https://etna.math.kent.edu/vol.40.2013/pp489-506.dir/pp489-506.pdf

    work page 2013

  17. [17]

    Golub and Charles F

    Gene H. Golub and Charles F. Van Loan. Matrix computations. The Johns Hopkins University Press, Baltimore, 2013. doi:10.56021/9781421407944

    work page doi:10.56021/9781421407944 2013

  18. [18]

    Iterative Solution of Large Sparse Systems of Equations , volume 95 of Applied Mathematical Sciences

    Wolfgang Hackbusch. Iterative Solution of Large Sparse Systems of Equations , volume 95 of Applied Mathematical Sciences . Springer International Publishing, Cham, 2016. doi: 10.1007/978-3-319-28483-5

    work page doi:10.1007/978-3-319-28483-5 2016

  19. [19]

    Nicholas J. Higham. Accuracy and stability of numerical algorithms. SIAM, Philadelphia, PA,

    work page

  20. [20]

    doi:10.1137/1.9780898718027

    work page doi:10.1137/1.9780898718027

  21. [21]

    Horn and C.R

    Roger A. Horn and Charles R. Johnson. Matrix analysis. Cambridge university press, Cam- bridge, 2012. doi:10.1017/CBO9781139020411

    work page doi:10.1017/cbo9781139020411 2012

  22. [22]

    Historical perspectives of the Riccati equations

    Marc Jungers. Historical perspectives of the Riccati equations. IFAC-PapersOnLine, 50(1):9535–9546, 2017. doi:10.1016/j.ifacol.2017.08.1619

    work page doi:10.1016/j.ifacol.2017.08.1619 2017

  23. [23]

    Kaniel and J

    S. Kaniel and J. Stein. Least-square acceleration of iterative methods for linear equations. J. Opt. Th. Appl. , 14:431–437, 1974. doi:10.1007/BF00933309

    work page doi:10.1007/bf00933309 1974

  24. [24]

    Low-rank updates and a divide-and- conquer method for linear matrix equations

    Daniel Kressner, Stefano Massei, and Leonardo Robol. Low-rank updates and a divide-and- conquer method for linear matrix equations. SIAM J. Sci. Comput. , 41(2):A848–A876, 2019. doi:10.1137/17M1161038

    work page doi:10.1137/17m1161038 2019

  25. [25]

    Algebraic Riccati equations

    Peter Lancaster and Leiba Rodman. Algebraic Riccati equations. Oxford Science Publica- tions. The Clarendon Press, Oxford University Press, New York, 1995. doi:10.1093/oso/ 9780198537953.001.0001

    work page doi:10.1093/oso/ 1995

  26. [26]

    Low rank solution of Lyapunov equations

    Jing-Rebecca Li and Jacob White. Low rank solution of Lyapunov equations. SIAM J. Matrix Anal. Appl., 24(1):260–280, 2002. doi:10.1137/S0895479801384937

    work page doi:10.1137/s0895479801384937 2002

  27. [27]

    A new subspace iteration method for the algebraic Riccati equation

    Yiding Lin and Valeria Simoncini. A new subspace iteration method for the algebraic Riccati equation. Numer. Lin. Alg. Appl. , 22(1):26–47, 2015. doi:10.1002/nla.1936

    work page doi:10.1002/nla.1936 2015

  28. [28]

    Opmeer, and Timo Reis

    Arash Massoudi, Mark R. Opmeer, and Timo Reis. Analysis of an iteration method for the algebraic Riccati equation. SIAM J. Matrix Anal. Appl. , 37(2):624–648, 2016. doi: 10.1137/140985792. Preprint. 2025-12-11 30

    work page doi:10.1137/140985792 2016

  29. [29]

    Convergence acceleration for the iterative solution of the equations X = AX + f

    Mari´ an Meˇ sina. Convergence acceleration for the iterative solution of the equations X = AX + f. Comp. Meth. Appl. Mech. Eng. , 10(2):165–173, 1977. doi:10.1016/0045-7825(77) 90004-4

    work page doi:10.1016/0045-7825(77 1977

  30. [30]

    Rudnyi, Andreas Greiner, and Jan G

    Christian Moosmann, Evgenii B. Rudnyi, Andreas Greiner, and Jan G. Korvink. Model order reduction for linear convective thermal flow. In Proceedings of 10th International Workshops on THERMal INvestigations of ICs and Systems , 2004. URL: http://modelreduction. rudnyi.ru/doc/papers/moosmann04THERMINIC.pdf

    work page 2004

  31. [31]

    Steel profile

    Oberwolfach Benchmark Collection. Steel profile. hosted at MOR Wiki – Model Order Re- duction Wiki, 2005. URL: http://modelreduction.org/index.php/Steel_Profile

    work page 2005

  32. [32]

    A cyclic low-rank Smith method for large sparse Lyapunov equations

    Thilo Penzl. A cyclic low-rank Smith method for large sparse Lyapunov equations. SIAM J. Sci. Comput., 21(4):1401–1418, 1999. doi:10.1137/S1064827598347666

    work page doi:10.1137/s1064827598347666 1999

  33. [33]

    Convergence acceleration of iterative sequences

    P´ eter Pulay. Convergence acceleration of iterative sequences. the case of SCF iteration.Chem. Phys. Lett., 73(2):393–398, 1980. doi:10.1016/0009-2614(80)80396-4

    work page doi:10.1016/0009-2614(80)80396-4 1980

  34. [34]

    Improved SCF convergence acceleration.J

    P´ eter Pulay. Improved SCF convergence acceleration.J. Comput. Chem., 3(4):556–560, 1982. doi:10.1002/jcc.540030413

    work page doi:10.1002/jcc.540030413 1982

  35. [35]

    A flexible inner-outer preconditioned GMRES algorithm

    Youcef Saad. A flexible inner-outer preconditioned GMRES algorithm. SIAM J. Sci. Comput., 14(2):461–469, 1993. doi:10.1137/0914028

    work page doi:10.1137/0914028 1993

  36. [36]

    Acceleration methods for fixed-point iterations

    Youcef Saad. Acceleration methods for fixed-point iterations. Acta Numerica, 34:805–890,

    work page

  37. [37]

    doi:10.1017/S0962492924000096

    work page doi:10.1017/s0962492924000096

  38. [38]

    Youcef Saad and Martin H. Schultz. GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Comput. , 7(3):856–869, 1986. doi: 10.1137/0907058

    work page doi:10.1137/0907058 1986

  39. [39]

    J. Saak, M. K¨ ohler, and P. Benner. M-M.E.S.S. – the Matrix Equations Sparse Solvers library. see also: https://www.mpi-magdeburg.mpg.de/projects/mess. doi:10.5281/ zenodo.632897

    work page

  40. [40]

    Derivatives on graphs for the positive calculus of relations with transitive closure, 2024

    Jonas Schulze and Jens Saak. An extension of the low-rank Lyapunov ADI to non-zero initial values and its applications. e-print 2406.13477, arXiv, 2024. math.NA. doi:10.48550/arXiv. 2406.13477

    work page internal anchor Pith review doi:10.48550/arxiv 2024

  41. [41]

    Some comments on the DIIS method

    Ron Shepard and Michael Minkoff. Some comments on the DIIS method. Mol. Phys., 105(19- 22):2839–2848, 2007. doi:10.1080/00268970701691611

    work page doi:10.1080/00268970701691611 2007

  42. [42]

    Extrapolation vs

    Avram Sidi. Extrapolation vs. projection methods for linear systems of equations. J. Comput. Appl. Math., 22(1):71–88, 1988. doi:10.1016/0377-0427(88)90289-0

    work page doi:10.1016/0377-0427(88)90289-0 1988

  43. [43]

    Efficient implementation of minimal polynomial and reduced rank extrapola- tion methods

    Avram Sidi. Efficient implementation of minimal polynomial and reduced rank extrapola- tion methods. J. Comput. Appl. Math. , 36(3):305–337, 1991. doi:10.1016/0377-0427(91) 90013-A

    work page doi:10.1016/0377-0427(91 1991

  44. [44]

    Practical extrapolation methods: Theory and applications, volume 10

    Avram Sidi. Practical extrapolation methods: Theory and applications, volume 10. Cambridge university press, Cambridge, 2003. doi:10.1017/CBO9780511546815

    work page doi:10.1017/cbo9780511546815 2003

  45. [45]

    A convergence study for reduced rank extrapolation on nonlinear systems.Numer

    Avram Sidi. A convergence study for reduced rank extrapolation on nonlinear systems.Numer. Algorithms, 84:957–982, 2020. doi:10.1007/s11075-019-00788-6

    work page doi:10.1007/s11075-019-00788-6 2020

  46. [46]

    Upper bounds for convergence rates of vector extrapolation methods on linear systems with initial iterations

    Avram Sidi and Yair Shapira. Upper bounds for convergence rates of vector extrapolation methods on linear systems with initial iterations. Technical report, National Aeronautics and Space Administration, 1992. Technical Memorandum 105608, ICOMP-92-09. URL: https: //ntrs.nasa.gov/citations/19920024498

    work page arXiv 1992

  47. [47]

    UCQ-shaped

    Avram Sidi and Yair Shapira. Upper bounds for convergence rates of acceleration meth- ods with initial iterations. Numer. Algorithms , 18(2):113–132, 1998. doi:10.1023/A: 1019113314010. Preprint. 2025-12-11 31

    work page doi:10.1023/a: 1998

  48. [48]

    Analysis of the rational Krylov subspace projection method for large- scale algebraic Riccati equations

    Valeria Simoncini. Analysis of the rational Krylov subspace projection method for large- scale algebraic Riccati equations. SIAM J. Matrix Anal. Appl. , 37(4):1655–1674, 2016. doi: 10.1137/16M1059382

    work page doi:10.1137/16m1059382 2016

  49. [49]

    Computational Methods for Linear Matrix Equations

    Valeria Simoncini. Computational Methods for Linear Matrix Equations. SIAM Rev. , 58(3):377–441, 2016. doi:10.1137/130912839

    work page doi:10.1137/130912839 2016

  50. [50]

    Convective thermal flow

    The MOR Wiki Community. Convective thermal flow. MOR Wiki – Model Order Reduction Wiki, 2018. URL: http://modelreduction.org/index.php/Convection

    work page 2018

  51. [51]

    An efficient method for estimating the optimal dampers’ viscosity for linear vibrating systems using Lyapunov equation

    Ninoslav Truhar and Kreˇ simir Veseli´ c. An efficient method for estimating the optimal dampers’ viscosity for linear vibrating systems using Lyapunov equation. SIAM J. Matrix Anal. Appl. , 31(1):18–39, 2009. doi:10.1137/070683052

    work page doi:10.1137/070683052 2009

  52. [52]

    Thomas Wolf and Heiko K. F. Panzer. The ADI iteration for Lyapunov equations implic- itly performs H2 pseudo-optimal model order reduction. International Journal of Control , 89(3):481–493, 2016. doi:10.1080/00207179.2015.1081985

    work page doi:10.1080/00207179.2015.1081985 2016

  53. [53]

    Young and Kang C

    David M. Young and Kang C. Jea. Generalized conjugate-gradient acceleration of non- symmetrizable iterative methods. Linear Algebra Appl. , 34:159–194, 1980. doi:10.1016/ 0024-3795(80)90165-2. Preprint. 2025-12-11

    work page 1980