Finding the maximum eigenvalue of a symmetric tensor is an important topic in tensor computation and numerical multilinear algebra. In this paper, we introduce a new class of structured tensors called W-tensors, which not only extends thewell-studied nonnegative tensors by allowing negative entries but also covers several important tensors arising naturally from spectral hypergraph theory.We then show that finding the maximum H-eigenvalue of an even-order symmetric W-tensor is equivalent to solving a structured semidefinite program and hence can be validated in polynomial time. This yields a highly efficient semidefinite program algorithm for computing themaximumH-eigenvalue of W-tensors and is based on a new structured sums-of-squares decomposition result for a nonnegative polynomial induced by W-tensors. Numerical experiments illustrate that the proposed algorithm can successfully find the maximum H-eigenvalue of W-tensors with dimension up to 10,000, subject to machine precision. As applications, we provide a polynomial time algorithm for computing the maximum H-eigenvalues of large-size Laplacian tensors of hyperstars and hypertrees, where the algorithm can be up to 13 times faster than the state-of-the-art numerical method introduced by Ng, Qi, and Zhou in 2009. Finally, we also show that the proposed 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.

In this paper, we focus on the stochastic inverse eigenvalue problem of reconstructing a stochastic matrix from the prescribed spectrum. We directly reformulate the stochastic inverse eigenvalue problem as a constrained optimization problem over several matrix manifolds to minimize the distance between isospectral matrices and stochastic matrices. Then we propose a geometric Polak–Ribi`ere–Polyak-based nonlinear conjugate gradient method for solving the constrained optimization problem. The global convergence of the proposed method is established. Our method can also be extended to the stochastic inverse eigenvalue problem with prescribed entries. An extra advantage is that our models yield new isospectral flow methods. Finally, we report some numerical tests to illustrate the efficiency of the proposed method for solving the stochastic inverse eigenvalue problem and the case of prescribed entries.

We consider the solution of large-scale discrete-time algebraic Riccati equations with numerically low-ranked solutions. The structure-preserving doubling algorithm will be adapted, with the iterates for A not explicitly computed but in the recursive form Ak= A2 k 1 D (1) k

No abstract uploaded!

The standard Yee's scheme for the Maxwell eigenvalue problems places the discrete electric field variable at the midpoints of the edges of the grid cells. It performs well when the permittivity is a scalar field. However, when the permittivity is a Hermitian full tensor filed it would generate un-physical complex eigenvalues or frequencies. In this paper, we propose a finite element method which can be interpreted as a modified Yee's scheme to overcome this difficulty. This interpretation enables us to create a fast FFT eigensolver that can compute very effectively the band structure of the anisotropic photonic crystal with SC and FCC lattices. Furthermore, we overcome the usual large null space associated with the Maxwell eigenvalue problem by deriving a null-space free discrete eigenvalue problem which involves a crucial Hermitian positive definite linear system to be solved in each of the iteration steps. It is demonstrated that the CG method without preconditioning converges in 37 iterations even when the dimension of the matrix is as large as $5,184,000$.

No abstract uploaded!

No abstract uploaded!

In this paper, we first study \ell_q minimization and its associated iterative reweighted algorithm for recovering sparse vectors. Unlike most existing work, we focus on <i>unconstrained</i> \ell_q minimization, for which we show a few advantages on noisy measurements and/or approximately sparse vectors. Inspired by the results in [Daubechies et al., <i>Comm. Pure Appl. Math.</i>, 63 (2010), pp. 1--38] for <i>constrained</i> \ell_q minimization, we start with a preliminary yet novel analysis for <i>unconstrained</i> \ell_q minimization, which includes convergence, error bound, and local convergence behavior. Then, the algorithm and analysis are extended to the recovery of low-rank matrices. The algorithms for both vector and matrix recovery have been compared to some state-of-the-art algorithms and show superior performance on recovering sparse vectors and low-rank matrices.

No abstract uploaded!

We propose an inverse iterative method for computing the Perron pair of an irreducible nonnegative third order tensor. The method involves the selection of a parameter $\theta_k$ in the $k$th iteration. For every positive starting vector, the method converges quadratically and is positivity preserving in the sense that the vectors approximating the Perron vector are strictly positive in each iteration. It is also shown that $\theta_k=1$ near convergence. The computational work for each iteration of the proposed method is less than four times (three times if the tensor is symmetric in modes two and three, and twice if we also take the parameter to be $1$ directly) that for each iteration of the Ng--Qi--Zhou algorithm, which is linearly convergent for essentially positive tensors.