Complexity reduction through a Schur-based decomposition for reachability analysis of linear time-invariant systems

Abstract

This article presents a method for complexity reduction in reachability analysis and safety-preserving controller synthesis via Schur-based decomposition. The decomposition results in either decoupled or weakly-coupled (lower dimensional) subsystems. Reachable sets, computed independently for each subsystem, are back-projected and intersected to yield an overapproximation of the actual reachable set. Moreover, applying this technique to a class of unstable LTI systems, we show that when certain eigenvalue and state-constraint conditions are satisfied, further reduction of complexity is possible. Evaluating our method for a variety of examples we demonstrate that significant reduction in the computational costs can be achieved. This technique has considerable potential utility for use in conjunction with computationally intensive reachability tools.