Graph Decomposition Methods for Uncertainty Propagation in Complex, Nonlinear Interconnected Dynamical Systems

Abstract—Uncertainty propagation in complex, intercon-nected dynamical systems systems can be performed more efficiently by decomposing the network based on the hierarchy and/or the strength of coupling. In this paper, we first present a structural decomposition method that identifies the hierarchy of subsystems. We briefly review the notion of horizontal– vertical decomposition (HVD) or strongly connected compo-nents (SCC) decomposition of a dynamical system and describe algorithms based on Markov chain theory and graph theory to obtain the HVD from the equation graph of the system. We also present a non-structural decomposition method to identify the weakly connected subsystems of a system based on the Laplacian of a graph derived from the Jacobian. While most of prior efforts in this direction concentrated on stability, robustness and concrete results were limited to linear systems, we use it for uncertainty propagation and study of asymptotic behavior of nonlinear interconnected systems. We illustrate the two methods using a fuel cell system example. These two methods provide a framework for efficient propagation of uncertainty in complex nonlinear systems. I