We introduceM-tensors. This concept extends the concept ofM-matrices. We denote Z-tensors as the tensors with nonpositive off-diagonal entries. We show that M-tensors must be Ztensors and the maximal diagonal entry must be nonnegative. The diagonal elements of a symmetric M-tensor must be nonnegative. A symmetric M-tensor is copositive. Based on the spectral theory of nonnegative tensors, we show that the minimal value of the real parts of all eigenvalues of an Mtensor is its smallest H+-eigenvalue and also is its smallest H-eigenvalue. We show that a Z-tensor is an M-tensor if and only if all its H+-eigenvalues are nonnegative. Some further spectral properties of M-tensors are given. We also introduce strong M-tensors, and some corresponding conclusions are given. In particular, we show that all H-eigenvalues of strong M-tensors are positive. We apply this property to study the positive definiteness of a class of multivariate forms associated with Z-tensors. We also propose an algorithm for testing the positive definiteness of such a multivariate form.

No abstract uploaded!

The doubling algorithms are very efficient iterative methods for computing the unique minimal nonnegative solution to an M-matrix algebraic Riccati equation (MARE). They are globally and quadratically convergent, except for MARE in the critical case where convergence is linear with the linear rate 1/2. However, the initialization phase and the doubling iteration kernel of any doubling algorithm involve inverting nonsingular M-matrices. In particular, for MARE in the critical case, the M-matrices in the doubling iteration kernel, although nonsingular, move towards singular M-matrices at convergence. These inversions are causes of concerns on entrywise relative accuracy of the eventually computed minimal nonnegative solution. Fortunately, a nonsingular M-matrix can be inverted by the GTH-like algorithm of Alfa, Xue, and Ye [Math. Comp., 71:217--236, 2002] to almost full entrywise relative accuracy, provided a triplet representation of the matrix is known. Recently, Nguyen and Poloni [Numer. Math., 130(4):763--792, 2015] discovered a way to construct triplet representations in a cancellation-free manner for all involved M-matrices in the doubling iteration kernel, for a special class of MAREs arising from Markov-modulated fluid queues. In this paper, we extend Nguyen's and Poloni's work to all MAREs by also devising a way to construct the triplet representations cancellation-free. Our construction, however, is not a straightforward extension of theirs. It is made possible by an introduction of novel recursively computable auxiliary nonnegative vectors. As the second contribution, we propose an entrywise relative residual for an approximate solution. The residual has an appealing feature of being able to reveal the entrywise relative accuracies of all entries, large and small, of the approximation. This is in marked contrast to the usual legacy normalized residual which reflects relative accuracies of large entries well but not so much those of very tiny entries. Numerical examples are presented to demonstrate and confirm our claims.

No abstract uploaded!

No abstract uploaded!