Matrix-Valued Linear Positive Operators and Applications to Graph Optimization

In this paper, we extend some general results on linear positive operators to the case of matrix-valued operators taking values in certain spaces of Hermitian matrices. These results are then used to show that certain matrices are optimal preconditioners for the linear systems arising in Interior Point methods for Linear Programs. In the case of graph matrices, corresponding to Min Cost Flow problems, we are able to find superlinear preconditioners for a class of ``local'' graphs generalizing the grid graphs commonly used in applications. For general graphs, we are able to give a spectral characterization of the preconditioners that may have a theoretical interest in its own.