Over the last few years sum of squares (SOS) programming has found application in the analysis of systems described by nonlinear differential equations through the algorithmic construction of Lyapunov functions. Unfortunately, even with worst-case polynomial time complexity, the analysis of nonlinear systems using SOS programming does not scale well as the number of system states increases. In this work we describe a methodology based on graph decomposition that allows for the analysis of sys...