Sparse decompositions of nonlinear dynamical systems and applications to moment-sum-of-squares relaxations

In this paper, we propose a general sparse decomposition of dynamical systems provided that the vector field and constraint set possess certain sparse structures, which we call subsystems. This notion is based on causal dependence in the dynamics between the different states. This results in sparse descriptions for fundamental problems from nonlinear dynamical systems: region of attraction, maximum positively invariant set, and global attractor. The decompositions can be paired with any method for computing (outer) approximations of these sets to reduce the computation to lower dimensional systems. This is illustrated by methods from previous work based on infinite-dimensional linear programming. This exhibits one example where the curse of dimensionality is present and hence dimension reduction is crucial. In this context, for polynomial dynamics, we show that these problems admit a sparse sum-of-squares (SOS) approximation with guaranteed convergence such that the number of variables in the largest SOS multiplier is given by the dimension of the largest subsystem appearing in the decomposition. The dimension of such subsystems depends on the sparse structure of the vector field and the constraint set; if the dimension of the largest subsystem is small compared to the ambient dimension, this allows for a significant reduction in the computation time of the SOS approximations. Numerical examples accompany the approach.