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

DOI10.1016/J.AUTOMATICA.2016.06.002MaRDI QIDQ2409310zbMATH OpenOpenAlexFDO

Authors Aleksandar Haber, Michel Verhaegen

Publication date 11 October 2017

Published in Automatica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.3898

zbMATH Keywords

complex systemslarge-scale Lyapunov equationlarge-scale optimization problems and methodsremote and distributed control

Mathematics Subject Classification ID

Decentralized systems (93A14) Large-scale systems (93A15) Linear systems in control theory (93C05)

Abstract: We consider the problem of computing an approximate banded solution of the continuous-time Lyapunov equation $underlineAunderlineX+underlineXunderline{A}^T=underlineP$, where the coefficient matrices $underlineA$ and $underlineP$ are large, symmetric banded matrices. The (sparsity) pattern of $underlineA$ describes the interconnection structure of a large-scale interconnected system. Recently, it has been shown that the entries of the solution $underlineX$ are spatially localized or decaying away from a banded pattern. We show that the decay of the entries of $underlineX$ is faster if the condition number of $underlineA$ is smaller. By exploiting the decay of entries of $underlineX$, we develop two computationally efficient methods for approximating $underlineX$ by a banded matrix. For a well-conditioned and sparse banded $underlineA$, 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 $underlineA$ and $underlineP$ 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.

Recommendations

• Approximate solution of large sparse Lyapunov equations
• scientific article; zbMATH DE number 2090653
• Iterative methods for solving large sparse Lyapunov equations and application to model reduction of index 1 differential-algebraic-equations
• Robust Stability Analysis of Sparsely Interconnected Uncertain Systems
• Parallel Solution of Large Lyapunov Equations
• scientific article; zbMATH DE number 1749779
• A New Iterative Method for Solving Large-Scale Lyapunov Matrix Equations
• Efficient Solution of Linearly Coupled Lyapunov Equations
• Efficient solution of large scale Lyapunov and Riccati equations arising in model order reduction problems
• On the numerical solution of large-scale sparse discrete-time Riccati equations

Cites work

• A Fast Newton's Method for a Nonsymmetric Algebraic Riccati Equation
• A Priori Sparsity Patterns for Parallel Sparse Approximate Inverse Preconditioners
• A Sparse Approximate Inverse Preconditioner for Nonsymmetric Linear Systems
• An Improved Newton Iteration for the Generalized Inverse of a Matrix, with Applications
• Approximate Inverse Preconditioners via Sparse-Sparse Iterations
• Approximate sparsity patterns for the inverse of a matrix and preconditioning
• ARPACK Users' Guide
• Augmented Lagrangian Approach to Design of Structured Optimal State Feedback Gains
• Bounds for the entries of matrix functions with applications to preconditioning
• Chebyshev series expansion of inverse polynomials
• Coherence in Large-Scale Networks: Dimension-Dependent Limitations of Local Feedback
• Communication Delay Co-Design in $\mathcal{ H}_{2}$-Distributed Control Using Atomic Norm Minimization
• Coordinated One-Step Optimal Distributed State Prediction for a Networked Dynamical System
• Decay bounds and \(O(n)\) algorithms for approximating functions of sparse matrices
• Decay bounds for functions of Hermitian matrices with banded or Kronecker structure
• Decay Rates for Inverses of Band Matrices
• Design of Low-Bandwidth Spatially Distributed Feedback
• Design of Optimal Sparse Feedback Gains via the Alternating Direction Method of Multipliers
• Design of structured dynamic output-feedback controllers for interconnected systems
• Distributed control design for spatially interconnected systems
• Distributed control of spatially invariant systems
• Distributing the Kalman Filter for Large-Scale Systems
• Efficient approximation of the exponential operator for discrete 2D advection–diffusion problems
• Efficient computation of the exponential operator for large, sparse, symmetric matrices
• Efficient solution of large-scale saddle point systems arising in Riccati-based boundary feedback stabilization of incompressible Stokes flow
• Filtering and System Identification
• Fundamental Limits and Tradeoffs on Disturbance Propagation in Linear Dynamical Networks
• scientific article; zbMATH DE number 1206370 (Why is no real title available?)
• scientific article; zbMATH DE number 2166998 (Why is no real title available?)
• scientific article; zbMATH DE number 1862742 (Why is no real title available?)
• scientific article; zbMATH DE number 852536 (Why is no real title available?)
• Inexact Kleinman-Newton method for Riccati equations
• Lyapunov matrix equations in system stability and control.
• Numerical solution of algebraic Riccati equations.
• Numerical solution of large and sparse continuous time algebraic matrix Riccati and Lyapunov equations: a state of the art survey
• Numerical solution of large-scale Lyapunov equations, Riccati equations, and linear-quadratic optimal control problems.
• On inexact Newton methods based on doubling iteration scheme for symmetric algebraic Riccati equations
• On the controllability and observability of networked dynamic systems
• On the decay of the inverse of matrices that are sum of Kronecker products
• On the finite section method for computing exponentials of doubly-infinite skew-Hermitian matrices
• On the ill-posedness of certain vehicular platoon control problems
• On the numerical solution of large-scale sparse discrete-time Riccati equations
• Optimal Control of Spatially Distributed Systems
• Parallel iterative methods for sparse linear systems
• Robust Stability Analysis of Sparsely Interconnected Uncertain Systems
• Solution of large scale algebraic matrix Riccati equations by use of hierarchical matrices
• Subspace Identification of Large-Scale Interconnected Systems
• The autonomous linear quadratic control problem. Theory and numerical solution
• Weighted steepest descent method for solving matrix equations

Cited in

(15)

• Sparsity preserving optimal control of discretized PDE systems
• Some algorithms for maximum volume and cross approximation of symmetric semidefinite matrices
• Decay bounds for functions of Hermitian matrices with banded or Kronecker structure
• Localization in matrix computations: theory and applications
• A Krylov subspace method for the approximation of bivariate matrix functions
• Stability analysis of interconnected nonlinear fractional-order systems via a single-state variable control
• Numerical Methods for Large-Scale Lyapunov Equations with Symmetric Banded Data
• Solving rank-structured Sylvester and Lyapunov equations
• Low-Rank Updates and a Divide-And-Conquer Method for Linear Matrix Equations
• Input matrix construction and approximation using a graphic approach
• Stochastic optimization of large-scale parametrized dynamical systems
• Finding Hankel singular values for singularly perturbed linear continuous-time systems
• Optimal network control of spatially exponential decaying linear quadratic regulator
• Global network control from local information
• Separable approximations of optimal value functions and their representation by neural networks

Describes a project that uses

Uses Software

• ARPACK

This page was built for publication: Sparse solution of the Lyapunov equation for large-scale interconnected systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2409310)