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

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. It gives rise to sparse descriptions for fundamental problems from nonlinear dynamical systems: The characterization of the region of attraction, the maximum positively invariant set, and the global attractor. The decompositions can be paired with any method for computing (outer) approximations of these sets, and reduce the task to lower dimensional systems. We illustrate this 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 convergent sparse sum-of-squares (SOS) approximations. We illustrate the computational benefit with numerical toy examples.