  In this thesis, we focus on some of the NP-hard problems in control theory.
Thanks to the converse Lyapunov theory, these problems can often be modeled as
optimization over polynomials. To avoid the problem of intractability, we
establish a trade off between accuracy and complexity. We develop a sequence of
tractable optimization problems - in the form of LPs and SDPs - whose solutions
converge to the exact solution of the NP-hard problem. However, the
computational and memory complexity of these LPs and SDPs grow exponentially
with the progress of the sequence - meaning that improving the accuracy of the
solutions requires solving SDPs with tens of thousands of decision variables
and constraints. Setting up and solving such problems is a significant
challenge. The existing optimization algorithms and software are only designed
to use desktop computers or small cluster computers - machines which do not
have sufficient memory for solving such large SDPs. This in fact is the reason
we seek parallel algorithms for setting-up and solving large SDPs on
supercomputers.
  We propose parallel algorithms for stability analysis of two classes of
systems: 1) Linear systems with a large number of uncertain parameters; 2)
Nonlinear systems defined by polynomial vector fields. First, we develop a
distributed parallel algorithm which applies Polya's and Handelman's theorems
to some variants of parameter-dependent Lyapunov inequalities with parameters
defined over the simplex. The result is a sequence of SDPs which possess a
block-diagonal structure. We then develop a parallel SDP solver which exploits
this structure to map the computation, memory and communication to a
distributed parallel environment. Numerical tests on a supercomputer
demonstrate the ability of the algorithm to efficiently utilize hundreds and
potentially thousands of processors and analyze systems with 100+ dimensional
state-space.
