  This paper discusses how to find the global minimum of functions that are
summations of small polynomials (``small'' means involving a small number of
variables). Some sparse sum of squares (SOS) techniques are proposed. We
compare their computational complexity and lower bounds with prior SOS
relaxations. Under certain conditions, we also discuss how to extract the
global minimizers from these sparse relaxations. The proposed methods are
especially useful in solving sparse polynomial system and nonlinear least
squares problems. Numerical experiments are presented, which show that the
proposed methods significantly improve the computational performance of prior
methods for solving these problems. Lastly, we present applications of this
sparsity technique in solving polynomial systems derived from nonlinear
differential equations and sensor network localization.
