Chordal sparsity, decomposing SDPs and the Lyapunov equation

Analysis questions in control theory are often formulated as Linear Matrix Inequalities and solved using convex optimisation algorithms. For large LMIs it is important to exploit structure and sparsity within the problem in order to solve the associated Semidefinite Programs efficiently. In this paper we decompose SDPs by taking advantage of chordal sparsity, and apply our method to the problem of constructing Lyapunov functions for linear systems. By choosing Lyapunov functions with a chordal graphical structure we convert the semidefinite constraint in the problem into an equivalent set of smaller semidefinite constraints, thereby facilitating the solution of the problem. The approach has the potential to be applied to other problems such as stabilising controller synthesis, model reduction and the KYP lemma.