A method for analyzing large-scale nonlinear dynamical systems by decomposing them into coupled lower order subsystems that are sufficiently simple for computational analysis is presented. It is shown that the decomposition approach can be used to scale the Sum of Squares programming framework for nonlinear systems analysis. The method constructs subsystem Lyapunov functions which are used to form a composite Lyapunov function for the whole system. Further computational savings are achieved if a method based on sparsity maximization is used to obtain the subsystem Lyapunov functions.