🔢 mathematics

Generalizing Reduced Rank Extrapolation to Low-Rank Matrix Sequences

This paper proposes two novel generalizations of Reduced Rank Extrapolation (RRE) to accelerate the iterative solution of large-scale matrix equations by adapting the method to handle sequences of low-rank matrices and fixed-point processes with iteration-varying mapping functions, demonstrating its effectiveness on Lyapunov and Riccati equations.

Original authors: Pascal den Boef, Patrick Kürschner, Xiaobo Liu, Jos Maubach, Jens Saak, Wil Schilders, Jonas Schulze, Nathan van de Wouw

Published 2026-05-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Pascal den Boef, Patrick Kürschner, Xiaobo Liu, Jos Maubach, Jens Saak, Wil Schilders, Jonas Schulze, Nathan van de Wouw

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the perfect spot to park a car in a very large, crowded lot. You don't know exactly where the empty spot is, so you take a guess, drive there, check if it's free, and if not, you adjust your position slightly and try again. You repeat this "guess-and-check" process over and over.

In the world of mathematics and engineering, this is called iterative solving. You start with a guess, apply a rule to get a better guess, and keep going until you are close enough to the answer.

However, sometimes this process is incredibly slow. You might be inching toward the parking spot, but every step is tiny, and it takes forever to get there. This is where the paper comes in.

The Problem: Slow Walkers and Changing Rules

The authors are dealing with two specific headaches that make this "parking" process even harder:

The "Huge" Problem: In many real-world engineering problems (like designing a car's suspension or a microchip's cooling system), the "map" of the parking lot is so massive that you can't even look at the whole thing at once. Instead, you only look at small, simplified sketches (called low-rank matrices) that capture the most important details. Standard methods for speeding up the process get confused when they try to look at these sketches instead of the full map.
The "Moving Goalpost" Problem: Usually, the rule you use to adjust your guess stays the same every time. But in these complex engineering problems, the rule changes with every single step. It's like trying to park, but the parking lot manager keeps changing the rules of how you are allowed to turn the steering wheel every time you move.

The Solution: The "Smart Navigator" (RRE)

The paper introduces a new, upgraded version of a technique called Reduced Rank Extrapolation (RRE). Think of RRE as a Smart Navigator that watches your "guess-and-check" steps.

Standard Navigator: If you are walking slowly, a standard navigator might say, "Okay, you moved 1 inch left, 1 inch forward. Let's just do that again."
The Smart Navigator (RRE): This navigator looks at your last few steps, sees the pattern, and says, "I see you are moving in a curve toward the spot. Instead of taking 10 more tiny steps, let's jump straight to where you would be if you kept that pattern!" This is called extrapolation—predicting the future based on the past to skip the boring middle steps.

What This Paper Actually Did

The authors didn't just invent a new navigator; they fixed two major bugs that prevented the navigator from working in these specific, difficult scenarios:

1. The "Sketch" Upgrade (Low-Rank Sequences)
Previously, the navigator could only work if you showed it the full, massive map. If you only gave it a small sketch (a low-rank matrix), it would crash or get stuck because the math was too heavy.

The Fix: The authors taught the navigator how to look only at the small sketches. They figured out a way to do the "jump" calculation using just the small pieces of information, making it fast and efficient even for the biggest problems.

2. The "Changing Rules" Upgrade (Non-Stationary Processes)
Previously, the navigator assumed the rules of the game never changed. If the rules changed every step (like the steering wheel rule changing), the navigator would get confused and start guessing wrong, sometimes even slowing you down.

The Fix: The authors rewrote the navigator's brain. Now, it looks at the actual error (how far off the guess is from the goal) rather than just how much the guess changed. This allows it to handle situations where the rules change at every step, keeping the acceleration effective even when the process is "non-stationary."

Putting It Together: The "Double-Upgrade"

The paper combines these two fixes into a single, powerful tool. They tested this new tool on real-world engineering equations (specifically Algebraic Riccati Equations and Lyapunov Equations), which are used to design control systems for things like aircraft, power grids, and microchips.

The Results:

In some cases, the standard method took 100 steps to get close enough to the answer.
With their new "Double-Upgrade" navigator, the same problem was solved in fewer steps (sometimes as few as 60 or 70).
They found that this method works best when the problem is "non-linear" (the rules are tricky) and when the "sketches" are small compared to the full problem size.

A Note on "Restarting"

The paper also discusses a strategy called "cycling," where the navigator takes a big jump, and then the driver starts a fresh set of guesses from that new spot. They found that while this works great for simple, linear problems, it can sometimes cause the driver to get stuck in a loop for complex, non-linear problems. They suggest that for the most complex problems, it might be safer to just keep taking the "smart jumps" without restarting the engine too often.

Summary

In short, this paper teaches a mathematical "Smart Navigator" how to:

Read small, simplified maps instead of huge ones.
Adapt when the rules of the game change every single turn.

By doing this, it helps engineers solve massive, complex design problems much faster than before, saving time and computing power.

Technical Summary: Generalizing Reduced Rank Extrapolation to Low-Rank Matrix Sequences

Problem Statement

Reduced Rank Extrapolation (RRE) is a well-established acceleration technique for iterative fixed-point processes generating vector sequences, typically used to solve nonlinear systems of equations $F(x)=0$ . However, its application to large-scale matrix equations presents two significant challenges that standard RRE cannot address directly:

Low-Rank Structure: In large-scale control theory problems (e.g., Algebraic Riccati Equations (AREs) and Lyapunov equations), the iterates $\{X_i\}$ are large matrices ( $d \times d$ ) that are computationally infeasible to store or vectorize. Instead, these iterates are maintained in a low-rank factorized form $X_i = Z_i D_i Z_i^T$ where the rank $z_i \ll d$ .
Nonstationary Fixed-Point Processes: Standard RRE assumes a stationary process $x_{i+1} = f(x_i)$ . However, many iterative solvers for matrix equations (such as RADI or ADI) utilize nonstationary processes $x_{i+1} = f_i(x_i)$ where the mapping function changes at every iteration (e.g., due to varying shift parameters). In such cases, the residual of the fixed-point iteration ( $f_i(x_i) - x_i$ ) no longer coincides with the residual of the underlying equation ( $F(x_i)$ ), leading to potential convergence issues if standard RRE is applied.

Methodology

The paper proposes two novel generalizations of RRE to address these challenges, which can be used independently or in combination.

1. RRE for Low-Rank Matrix Sequences

To avoid the prohibitive cost of vectorizing large matrices, the authors derive a formulation that operates directly on the low-rank factors.

Unitary Invariance: Leveraging Lemma 3.1, the authors show that the Frobenius or spectral norm of a symmetric matrix $\Delta$ is invariant under projection onto a subspace containing its range. This allows the optimization problem (minimizing the residual norm) to be solved in a reduced space of size $z \times z$ (where $z$ is the sum of the ranks of the iterates) rather than $d \times d$ .
Incremental Structure: For solvers like RADI and ADI, iterates are constructed via low-rank updates ( $X_{i+1} = X_i + V_{i+1} \tilde{D}_{i+1} V_{i+1}^T$ ). The authors exploit this structure to express the extrapolant as a weighted sum of these increments, further reducing computational complexity.
Algorithm 4: This algorithm computes the RRE weights using the thin QR-decomposition of the concatenated residual factors, avoiding the assembly of full matrices.

2. RRE for Nonstationary Fixed-Point Processes

The authors address the discrepancy between the fixed-point residual and the equation residual in nonstationary settings.

Residual Formulation: Instead of minimizing the norm of the difference between consecutive iterates ( $x_{i+1} - x_i$ ), the proposed method minimizes the norm of the underlying equation's residual $F(x_i)$ .
Algorithm 5 (RREF): This variant constructs the extrapolation matrix using the sequence of equation residuals $\{F(x_1), \dots, F(x_n)\}$ rather than the differences between iterates. This approach is shown to be necessary for nonstationary processes to maintain convergence speed, as demonstrated in a numerical example involving Successive Over-Relaxation (SOR) with varying parameters.

3. Combined Application to Large-Scale Matrix Equations

The paper integrates these extensions for solving large-scale AREs using the RADI method.

Algorithm 7 (RRELR_R): This algorithm combines the low-rank formulation with the nonstationary residual formulation. It utilizes the residual factors $R_i$ generated during the RADI iteration to compute the RRE weights.
Theoretical Properties: The authors prove (Theorem 3.1) that the residual of the extrapolant remains within the range of the concatenated residual factors of the input iterates, allowing for efficient evaluation of the residual norm without forming the full extrapolant.
Constraints on Coefficients: To ensure the extrapolated solution remains positive semi-definite (PSD)—a requirement for the stabilizing solution of AREs—the authors derive linear inequality constraints on the RRE weights. For a non-restarting scheme, $\sum_{j=i}^n \gamma_j \geq 0$ is sufficient. For restarting schemes, the authors conjecture that $0 \leq \gamma_i \leq 1$ is required to ensure the residual remains PSD.

Key Results

The proposed methods were evaluated on several large-scale sparse matrix equations, including:

Nonlinear AREs: Synthetic Toeplitz systems, a microelectronic chip model (chip), and a steel rail profile model.
Linear Lyapunov Equations: Derived from the same models by setting specific terms to zero.
Mechanical Systems: A triple chain mass-spring-damper system.

Findings:

Acceleration: In nonlinear AREs where the standard RADI method exhibits stagnation, the RRE-accelerated methods significantly reduced the number of iterations required to reach convergence (e.g., reducing iterations from 107 to 93 in the steel rail profile example).
Nonstationary Efficacy: The use of the equation residual (Algorithm 5) was critical for nonstationary processes; standard RRE (minimizing iterate differences) performed significantly worse or stagnated in nonstationary scenarios.
Cycling vs. Non-Cycling: While non-cycling modes generally improved convergence, cycling modes (restarting the process with the extrapolant) sometimes led to stagnation in nonlinear problems. The authors attribute this to the potential generation of non-PSD residuals upon restart, which violates the conditions required for RADI convergence.
Linear vs. Nonlinear: The acceleration was most pronounced in nonlinear cases. In linear Lyapunov equations, the standard ADI iterates were often already near-optimal, yielding modest gains from RRE.
Accuracy: On small-scale versions of the problems, the RRE solutions were verified to be extremely close to the exact stabilizing solutions (relative errors on the order of $10^{-9}$ to $10^{-14}$ ).

Significance and Claims

The paper claims to provide the first efficient schemes for applying RRE to:

Sequences of low-rank matrices without vectorization.
Iterates generated by nonstationary fixed-point processes.

The authors emphasize that their approach is non-intrusive regarding the underlying solver (it only requires access to iterates and residuals) but intrusive in the sense that it requires knowledge of the residual structure to be computationally efficient.

The significance lies in enabling the acceleration of iterative solvers for large-scale control problems (AREs and Lyapunov equations) where standard vector-based extrapolation is impossible due to memory constraints and where standard RRE fails due to the nonstationary nature of the shift parameters. The authors modestly note that while they provide convergence guarantees for the underlying RADI method, convergence guarantees for the RRE-accelerated nonlinear system remain an open theoretical challenge, particularly regarding the preservation of the PSD property in restarting schemes.

The work concludes that while RRE offers substantial potential for reducing iteration counts, particularly in nonlinear regimes, the computational overhead and the need for careful management of restarting conditions (to preserve PSD properties) must be balanced against the gains. Future work is suggested to focus on adaptive strategies for enabling RRE and deriving rigorous convergence guarantees for the nonlinear case.