From low-rank approximation to an efficient rational Krylov subspace method for the Lyapunov equation

D. A. Kolesnikov, Ivan OseledetsarXiv 2014 · DOI · arXiv

Abstract

We propose a new method for the approximate solution of the Lyapunov equation with rank-1 right-hand side, which is based on extended rational Krylov subspace approximation with adaptively computed shifts. The shift selection is obtained from the connection between the Lyapunov equation, solution of systems of linear ODEs and alternating least squares method for low-rank approximation. The numerical experiments confirm the effectiveness of our approach.

Introduction

The Lyapunov equation, defined as $AX + XA^\top = -y_0y_0^\top$, is a fundamental component in control theory, signal processing, and model order reduction. In modern applications involving large-scale systems—such as those arising from the discretization of 3D partial differential equations (PDEs)—the solution matrix $X$ is typically dense. Storing $X$ directly is computationally impossible for large $A$.

To address this, researchers seek a low-rank approximation $X \approx UZU^\top$, where $U$ is a thin basis matrix. The primary challenge in this field is "basis enrichment": determining which vectors to add to $U$ to minimize the approximation error most efficiently. While Rational Krylov Subspace Methods (RKSM) are widely used, their performance depends heavily on the selection of "shifts" (parameters for linear solves), which are often difficult to optimize dynamically.

The Alternating Low Rank (ALR) Method

This paper introduces the Alternating Low Rank (ALR) method, which utilizes an adaptive shift-selection strategy derived from a minimization problem. The method is built on three conceptual pillars:

1. The ODE Connection

The authors demonstrate that finding the optimal low-rank subspace for the Lyapunov equation is mathematically equivalent to minimizing the approximation error of a system of linear Ordinary Differential Equations (ODEs). This connection allows the use of optimization techniques typically reserved for time-dependent systems.

2. Gradient-Based Enrichment

Rather than relying on heuristic shift selection, the ALR method derives the gradient of an error functional. By using a rank-1 approximation of this gradient, the algorithm determines the next optimal shift to expand the subspace. This ensures that each addition to the basis is mathematically driven to maximize error reduction.

3. The ALR Algorithm

In each iteration, the algorithm performs the following steps:

  • Computes a standard Krylov vector via matrix-vector product.
  • Calculates an adaptive shift based on the current residual.
  • Solves a shifted linear system $(A + sI)v = w$ to generate a rational Krylov vector.
  • Updates the basis $U$ and the small-scale solution $Z$.

Computational Efficiency and AMG Integration

A significant bottleneck in rational Krylov methods is the requirement to solve large linear systems. The ALR method addresses this by integrating with Algebraic Multigrid (AMG) solvers.

Unlike traditional RKSM, where shifts are often widely distributed across the complex plane, the ALR method produces shifts that are more concentrated. This concentration is a major practical advantage: it allows the solver to reuse the same multigrid hierarchy and preconditioners across different shifts, drastically reducing the setup time and total computational overhead.

Numerical Experiments

The effectiveness of the ALR method was evaluated using four standard PDE-based model problems:

  • Laplace 2D & 3D: Symmetric matrices from the discretization of the Laplace operator.
  • Convection-Diffusion 2D & 3D: Non-symmetric matrices simulating heat flow with convection, involving complex eigenvalues.

Key Results

  • Execution Speed: In a 3D Laplace problem ($30 \times 30 \times 30$ grid), the ALR method combined with AMG reached a target accuracy of $10^{-8}$ in approximately 3 seconds. In contrast, standard RKSM required over 120 seconds to reach the same threshold.
  • Rank Efficiency: The method consistently achieves high accuracy with a very small basis rank (typically $r < 30$), even when the number of unknowns in the system reaches tens of thousands.
  • Robustness: The algorithm proved versatile, maintaining high performance across both symmetric and non-symmetric matrix structures.

Conclusion and Future Work

The ALR method bridges the gap between manifold-based optimization and subspace methods, providing a unified framework for solving large-scale Lyapunov equations. By producing concentrated adaptive shifts, it enables the efficient use of modern iterative solvers like AMG.

While highly effective for rank-1 right-hand sides, future research will focus on developing a "block version" of the algorithm to handle general rank-$k$ right-hand sides. Additionally, further theoretical work is needed to establish a rigorous convergence rate for this specific adaptive strategy and to evaluate the impact of using inexact linear solvers on the overall convergence of the method.

Summary updated

Abstract

We propose a new method for the approximate solution of the Lyapunov equation with rank-$1$ right-hand side, which is based on extended rational Krylov subspace approximation with adaptively computed shifts. The shift selection is obtained from the connection between the Lyapunov equation, solution of systems of linear ODEs and alternating least squares method for low-rank approximation. The numerical experiments confirm the effectiveness of our approach.
BibTeX
@misc{kolesnikov2014from,
  author = {D. A. Kolesnikov and Ivan Oseledets},
  title = {{From low-rank approximation to an efficient rational Krylov subspace method for the Lyapunov equation}},
  year = {2014},
  eprint = {1410.3335},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1410.3335},
}

Loading related content...

Figure