  Finding the maximum eigenvalue of a symmetric tensor is an important topic in
tensor computation and numerical multilinear algebra. This paper is devoted to
a semi-definite program algorithm for computing the maximum $H$-eigenvalue of a
class of tensors with sign structure called $W$-tensors. The class of
$W$-tensors extends the well-studied nonnegative tensors and essentially
nonnegative tensors, and covers some important tensors arising naturally from
spectral hypergraph theory. Our algorithm is based on a new structured
sums-of-squares (SOS) decomposition result for a nonnegative homogeneous
polynomial induced by a $W$-tensor. This SOS decomposition enables us to show
that computing the maximum $H$-eigenvalue of an even order symmetric $W$-tensor
is equivalent to solving a semi-definite program, and hence can be accomplished
in polynomial time. Numerical examples are given to illustrate that the
proposed algorithm can be used to find maximum $H$-eigenvalue of an even order
symmetric $W$-tensor with dimension up to $10,000$. We present two applications
for our proposed algorithm: we first provide a polynomial time algorithm for
computing the maximum $H$-eigenvalues of large size Laplacian tensors of
hyper-stars and hyper-trees; second, we show that the proposed SOS algorithm
can be used to test the copositivity of a multivariate form associated with
symmetric extended $Z$-tensors, whose order may be even or odd. Numerical
experiments illustrate that our structured semi-definite program algorithm is
effective and promising.
