Dynamical system decomposition for efficient, sparse analysis

We describe a system decomposition approach that allows for the efficient analysis of dynamical systems in the sum of squares (SOS) programming framework. The motivation is to break high-dimensional systems into lower-order interacting subsystems and to find a stability certificate for each of the subsystems. The certificates can be integrated at the end and used to determine the stability of the original large-scale system. Implicit in the decomposition approach is the requirement that each of the subsystems be stable. In this paper we show that under certain conditions, unstable decompositions can be analyzed by allowing non-disjoint, i.e. overlapping state partitions. A new method to reduce the number of decision variables in SOS programmes by maximizing the sparsity of the coefficients in the subsystem certificates is also presented.