Input matrix construction and approximation using a graphic approach
From MaRDI portal
Abstract: Given a state transition matrix (STM), we reinvestigate the problem of constructing the sparest input matrix with a fixed number of inputs to guarantee controllability. We give a new and simple graph theoretic characterization for the sparsity pattern of input matrices to guarantee controllability for a general STM admitting multiple eigenvalues, and provide a deterministic procedure with polynomial time complexity to construct real valued input matrices with arbi- trarily prescribed sparsity pattern satisfying controllability. Based on this criterion, some novel results on sparsely controlling a system are obtained. It is proven that the minimal number of inputs to guarantee controllability equals to the maximum geometric multiplicity of the STM under the constraint that some states are actuated-forbidden, extending the results of [28]. The minimal sparsity of input matrices with a fixed number of inputs is not necessarily equal to the minimal number of actuated states to ensure controllability. Furthermore, a graphic sub- modular function is built, leading to a greedy algorithm to efficiently approximate the minimal actuated states to assure controllability for general STMs. For the problem of approximating the sparsest input matrices with a fixed number of inputs, we propose a simple greedy algo- rithm (non-submodular) and a two-stage algorithm, and demonstrate that the latter algorithm, inspired from techniques in dynamic coloring, has a provable approximation guarantee. Finally, we present numerical results to show the efficiency and effectiveness of our approaches.
Recommendations
- scientific article; zbMATH DE number 4201485
- An exact method for triangularizing input-output matrixes
- The Solution to a Structured Matrix Approximation Problem Using GrassmanCoordinates
- scientific article; zbMATH DE number 1409215
- scientific article; zbMATH DE number 4081605
- Graph-matrix calculus for computational convex analysis
- Construction of matrices with a given graph and prescribed interlaced spectral data
- scientific article; zbMATH DE number 4165563
- Approximate iterations for structured matrices
- Publication:4938233
Cites work
- scientific article; zbMATH DE number 47926 (Why is no real title available?)
- A Framework for Structural Input/Output and Control Configuration Selection in Large-Scale Systems
- A Supermodular Optimization Framework for Leader Selection Under Link Noise in Linear Multi-Agent Systems
- An analysis of the greedy algorithm for the submodular set covering problem
- Controllability Analysis for a Networked Dynamic System With Autonomous Subsystems
- Controllability Metrics, Limitations and Algorithms for Complex Networks
- Generic properties and control of linear structured systems: A survey
- Interacting with Networks: How Does Structure Relate to Controllability in Single-Leader, Consensus Networks?
- Matroid intersection algorithms
- Maximum rank matrix completion
- Minimal Actuator Placement With Bounds on Control Effort
- Minimal Controllability Problems
- Minimal inputs/outputs for subsystems in a networked system
- On Submodularity and Controllability in Complex Dynamical Networks
- On the Stability and Robust Stability of Networked Dynamic Systems
- On the controllability and observability of networked dynamic systems
- Sparse solution of the Lyapunov equation for large-scale interconnected systems
- Structural controllability and matrix nets†
- Structure identification for gene regulatory networks via linearization and robust state estimation
- The robust minimal controllability problem
Cited in
(4)
This page was built for publication: Input matrix construction and approximation using a graphic approach
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5134304)
