Estimation of sparse hessian matrices and graph coloring problems

Large scale optimization problems often require an approximation to the Hessian matrix. If the Hessian matrix is sparse then estimation by differences of gradients is attractive because the number of required differences is usually small compared to the dimension of the problem. The problem of estimating Hessian matrices by differences can be phrased as follows: Given the sparsity structure of a symmetric matrixA, obtain vectorsd ₁,d ₂, …d _p such thatAd ₁,Ad ₂, …Ad _p determineA uniquely withp as small as possible. We approach this problem from a graph theoretic point of view and show that both direct and indirect approaches to this problem have a natural graph coloring interpretation. The complexity of the problem is analyzed and efficient practical heuristic procedures are developed. Numerical results illustrate the differences between the various approaches. Work supported in part by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38.     

Nonnegative Rank Factorization of a Nonnegative Matrix A with A A ≥0

In this article we obtain a nonnegative rank factorization of nonnegative matrices A satisfying one or both of the following conditions: (i) AA ? ? 0 (ii) A ? A ? 0, thus providing a new set of conditions that guarantee the existence of a nonnegative least-squares solution of a linear system. Indeed, the characterization of such matrices improves some of the previous known conditions for the existence of a nonnegative least-squares solution of a linear system.     

Sums and Products of Square-Zero Matrices

We show that for any two n × n square-zero matrices A and B over a division ring, if the right column spaces of AB and BA are the same, then the rank of AB is at most n/4, and if, in addition, the right null spaces of AB and BA are the same, then the rank of A + B is at most n/2. This generalizes some known results.     

Some decomposition results for a class of vacation queues

We analyze the MAP/PH/1 vacation system at arbitrary times using the matrix-analytic method, and obtain decomposition results for the R$R$ and G$G$ matrices. The decomposition results reduce the amount of computational effort needed to obtain these matrices. The results for the G$G$ matrix are extended to the BMAP/PH/1 system. We also show that in the case of the Geo/PH/1 and M/PH/1 systems with PH vacations both the G$G$ and R$R$ matrices can be obtained explicitly.