Source-linked AI summary
On bounds for rank growth of iterands in conjugate gradients for Lyapunov equation
Jana Lungová, Martin Plešinger
TL;DR
The paper studies rank growth in matrix conjugate gradients for Lyapunov equations, where the matrix A is assumed SPD. It establishes rank bounds for MCG iterands and reports an experiment in which the bound is tight and the theoretical maximum rank can be attained.
Problem
The paper examines how ranks of MCG iterands grow, including intermediate growth that limits low-rank arithmetic and is not fully understood.
Source: §3 · p. 2, §3.3 · p. 5Method
The paper applies matrix conjugate gradients to the Lyapunov equation and derives bounds for ranks of its iterands.
Source: §3 · p. 2, §4.3 · p. 8, This further bounds the ranks of… · p. 8Results
An experiment shows the rank bound is tight and the theoretical maximal allowed rank can be attained for a reasonable problem.
Source: §6 · p. 10Takeaways & Limitations
The ranks of MCG iterands are controlled by spectral properties of A, while MCG convergence depends on properties of the Lyapunov operator.
Source: §6 · p. 10The analysis assumes A is symmetric positive definite.
Source: §2 · p. 2
Abstract
from arXiv · showhide
We focus on solving the Lyapunov equation $AX + XA^T = F$, where $A$, $X$ and $F$ are square matrices, $A$ is symmetric positive definite (SPD) and sparse, and $F$ is symmetric and of a low-rank. The solution $X$ is then also symmetric and in general dense, but it can be approximated by a low-rank matrix. If $n$ is large, $X$ cannot be computed directly, but it is accessible by using the so-called low-rank arithmetics (LRA). The equation is solved by matrix reformulation of the method of conjugate gradients (MCG). We are interested in the behavior of ranks of the solution approximations $X_\ell$, residuals $R_\ell$, and direction vectors $P_\ell$ during iterations.
1. Introduction
The paper motivates Lyapunov equations through stability analysis of linear dynamical systems and their controllability and observability gramians. It introduces a matrix-form conjugate-gradient method for solving the equation.
1. Introduction
- For stable systems, controllability and observability are determined by gramians satisfying the Lyapunov equation.Source: §1 · p. 1
- The motivation comes from control theory and the stability of linear dynamical systems represented by differential equations [1].Source: §1 · p. 1
- The paper applies conjugate gradients in a special matrix form, MCG, to solve the Lyapunov equation.Source: §1 · p. 1
2. The Lyapunov equation
The section formulates the Lyapunov equation as a linear system and establishes conditions for its unique solvability and use of conjugate gradients. Under the SPD assumption on A, its Lyapunov operator is also SPD.
2. The Lyapunov equation
- The Lyapunov equation is LA(X) = AX + XAT = F, and vectorization gives LAx = f with LA = A ⊗ In + In ⊗ A.Source: §2 · pp. 1–2
- For symmetric F, transposition shows that XT is also a solution, so uniqueness implies the solution X is symmetric.Source: §2 · pp. 1–2
- Unique solvability of the Lyapunov equation is equivalent to regularity of LA.Source: §2 · p. 2
- Assuming A is SPD, the eigenvalues of LA are sums λi(A) + λj(A), making LA SPD and suitable for CG.Source: §2 · p. 2
- When the right-hand side is low-rank, the solution can be approximated by a low-rank matrix, supporting low-rank arithmetic.Source: §2 · p. 2
3. Matrix formulation of the conjugate gradient method (MCG)
MCG adapts conjugate gradients to matrix iterands for the Lyapunov equation, with rank growth arising in saxpy operations and applications of the Lyapunov operator. The experiment illustrates rank growth and stagnation, motivating the paper’s question about why growth stops before dimension n.
3. Matrix formulation of the conjugate gradient method (MCG)
- MCG replaces vectors with matrices and matrix-vector products with applications of the Lyapunov operator.Source: §3 · p. 2
3.1. Propagation of rank in saxpy operations
- In saxpy operations, rank is bounded by 2 max(rank(M), rank(N)), so it can double in the worst case; compression can control growth.The paper describes compression as rounding some eigenvalues to zero.Source: §3.1 · p. 3
3.2. Propagation of rank in application of Lyapunov operator LA
- Applying the Lyapunov operator produces a spectral-like decomposition that requires compression, and rank can double in the worst case at line 6.Compression is again identified as the place to control rank growth.Source: §3.2 · p. 4
3.3. Experiment
- In the experiment, the numerical rank of Xℓ grows rapidly, stagnates near 50 around iterations 100–200, then decreases as eigenvalues decay exponentially.The experiment uses a discretized 1D Laplace operator for A and a rank-one all-ones matrix for F.Source: §3.3 · p. 4, Figure 1 · p. 5
- The observed intermediate rank growth limits low-rank arithmetic, and preconditioners are a possible response, though the phenomenon is not fully understood.Source: §3.3 · p. 5
- The experiment asks why rank growth stops before reaching n = 100, after stagnation near rank 50.Source: §3.3 · pp. 4–5
4. Krylov subspaces with Lyapunov operator
The section connects matrix conjugate gradients to Krylov subspaces and uses that connection to bound the ranks of its iterands. For rank-one F = bbT, the bounds are expressed through Krylov-subspace dimensions generated by A and b.
4.1. Relations between Krylov subspaces generated by LA and LA
- MCG is the matrix form of standard CG under vectorization, connecting its iterands to Krylov subspaces generated by the Lyapunov operator.The section explicitly identifies MCG as the matricized form of standard CG.Source: §4.1 · p. 6
4.2. Relations between Krylov subspaces generated by LA and A
- Theorem 2 relates Krylov subspaces generated by LA and F to those generated by A and b through a column-selection mapping.The mapping is applied elementwise to the subspace, and the text introduces it as selecting a matrix column.Source: §4.2 · pp. 6–7
4.3. Krylov bound for ranks of iterands
- For rank-one F = bbT, Corollary 1 places the columns of Xℓ in Kℓ(A,b), and those of Rℓ and Pℓ in Kℓ+1(A,b).It places the columns of Wℓ in A Kℓ(A,b).Source: §4.3 · p. 8
This further bounds the ranks of individual iterands
- The resulting rank bounds are rank(Xℓ), rank(Wℓ) ≤ dim(Kℓ(A,b)) and rank(Rℓ), rank(Pℓ) ≤ dim(Kℓ+1(A,b)).The solution and W bounds use the current Krylov dimension; residual and direction bounds use the next dimension.Source: This further bounds the ranks of… · p. 8
5. Maximal number of iterations and maximal ranks of iterands in MCG
For the 1D Laplace experiment, the rank of Xℓ stagnates at 50 between iterations 100–200, matching the stated bound. The section relates maximal iteration counts to spectral properties and maximal iterand ranks to κA,b.
5. Maximal number of iterations and maximal ranks of iterands in MCG
- In exact arithmetic, classical CG with x0 = 0 converges in κA,b iterations, where κA,b counts the nonzero components of b across A's eigenspaces.κA,b is no greater than the number of distinct eigenvalues of A.Source: §5 · p. 8
5.1. Maximal number of iterations of MCG
- Exact MCG iteration counts depend on κLA,f; κA only bounds the distinct eigenvalues of LA, and κA = 3 can correspond to κLA = 5.The Lyapunov operator's eigenvalues cannot all be simple unless n = 1, and additional multiplicities can arise from particular eigenvalues of A.Source: §5.1 · p. 9
5.2. Maximal ranks of iterands in MCG
- Corollary 2 gives maximal-rank bounds for the MCG iterands in terms of κA,b.The section connects the behavior of classical CG to the bounds for individual MCG iterands.Source: §5.2 · p. 9
5.3. Back to the experiment
- rank(Xℓ) stagnated at 50 and did not exceed that bound between iterations 100–200 in the 1D Laplace experiment.The experiment uses a discretization of the 1D Laplace operator with Dirichlet boundary conditions and b equal to the all-ones vector.Source: §5.3 · p. 9
6. Conclusions
The paper establishes bounds on MCG iterand ranks for a rank-one right-hand side and reports that an experiment attains the theoretical maximal allowed rank.
6. Conclusions
- MCG iterand ranks are controlled by A's spectral properties, while convergence is governed by properties of the Lyapunov operator LA.The experiment shows the rank bound is tight and that the theoretical maximal allowed rank can be attained for a reasonable problem.Source: §6 · p. 10