Fast Algorithms for Computing Continuous Piecewise Affine Lyapunov Functions

Algorithms that parameterize continuous and piecewise affine Lyapunov functions for nonlinear systems, both in continuous and discrete time, have been proposed in numerous publications. These algorithms generate constraints that are linear in the values of a function at all vertices of a simplicial complex. If these constraints are fulfilled for certain values at the vertices, then they can be interpolated on the simplices to deliver a function that is a Lyapunov function for the system used for their generation. There are two different approaches to find values that fulfill the constraints. First, one can use optimization to compute appropriate values that fulfill the constraints. These algorithms were originally designed for continuous-time systems and their adaptation to discrete-time systems and control systems poses some challenges in designing and implementing efficient algorithms and data structures for simplicial complexes. Second, one can use results from converse theorems in the Lyapunov stability theory to generate good candidates for suitable values and then verify the constraints for these values. In this paper we study several efficient data structures and algorithms for these computations and discuss their implementations in C++.