Sparse solution of the Lyapunov equation for large-scale interconnected systems

Abstract

We consider the problem of computing an approximate banded solution of the continuous-time Lyapunov equation $\underline{A}\underline{X}+\underline{X}{\underline{A}}^T=\underline{P}$, where the coefficient matrices $\underline{A}$ and $\underline{P}$ are large, symmetric banded matrices. The (sparsity) pattern of $\underline{A}$ describes the interconnection structure of a large-scale interconnected system. Recently, it has been shown that the entries of the solution $\underline{X}$ are spatially localized or decaying away from a banded pattern. We show that the decay of the entries of $\underline{X}$ is faster if the condition number of $\underline{A}$ is smaller. By exploiting the decay of entries of $\underline{X}$, we develop two computationally efficient methods for approximating $\underline{X}$ by a banded matrix. For a well-conditioned and sparse banded $\underline{A}$, the computational and memory complexities of the methods scale linearly with the state dimension. We perform extensive numerical experiments that confirm this, and that demonstrate the effectiveness of the developed methods. The methods proposed in this paper can be generalized to (sparsity) patterns of $\underline{A}$ and $\underline{P}$ that are more general than banded matrices. The results of this paper open the possibility for developing computationally efficient methods for approximating the solution of the large-scale Riccati equation by a sparse matrix.

Accepted in Automatica, Final version, 16 pages, 10 figures

References in corpus (10)

• Revealing Network Connectivity From Dynamics
• Controllability transition and nonlocality in network control
• Robust Stability Analysis of Sparsely Interconnected Uncertain Systems
• Fundamental Limits and Tradeoffs on Disturbance Propagation in Large-Scale Dynamical Networks
• The Lyapunov matrix equation. Matrix analysis from a computational perspective
• Decay bounds for functions of matrices with banded or Kronecker structure
• Distributed Robustness Analysis of Interconnected Uncertain Systems Using Chordal Decomposition
• Sparse approximate inverses of Gramians and impulse response matrices of large-scale interconnected systems
• Subspace identification of large-scale interconnected systems
• Communication Delay Co-Design in ${\mathcal{H}}_2$ Distributed Control Using Atomic Norm Minimization

Cited by in corpus (1)

• The Lyapunov matrix equation. Matrix analysis from a computational perspective