Model-order reduction is an essential tool for large-scale systems introduced by modern Technologies for which full order simulation and controller design and implementation may be numerically and computationally infeasible. Model order reduction is a well established field of research in control and systems theory. Of particular interest in recent years is the study of model reduction for multi-agent systems which are characterized by their increasingly large scales.
Multi-agent systems have an underlying network structure represented by graphs. For large-scale graphs, combinatorial operations can be performed to obtain reduced graph sizes. In general, there is an interest to understand how certain graph reduction operations preserve spectral and combinatorial properties of the graph. We explore in this talk certain graph reductions that satisfy an interlacing property between spectral properties of graphs represented by matrices. We show how two types of graph contractions, cycle invariant contractions and node-removal equivalent contractions, lead to spectral interlacing of the normalized-Laplacian and Laplacian graph matrices, and we provide efficient algorithms for performing these contractions.
We then leverage these results on graph reductions to study model reduction of large-scale networked dynamic systems. We show how graph contractions can be used to obtain reduced-order models with guarantees on the performance of the reduced model compared to the original model. In this direction, we derive an a priori H2 error reduction bound for graph-based interlacing reduced models. We then demonstrate these results on the classical controlled consensus model.
