Algorithmic Aspects of Matrix Scaling and Related Problems

这个项目将研究矩阵缩放问题的算法方面。这些问题要求将给定的矩阵与两个对角矩阵进行前后乘法，以使得到的定标矩阵满足规定的条件。各种各样的实际和理论问题都属于矩阵缩放问题的一般框架。其中包括：(I)将非负矩阵按比例变换为规定的行列和；(Ii)按比例相似变换、平衡和矩阵预条件；(Iii)将非负矩阵按比例变换为规定的行列极大值；(Iv)按比例变换半正定矩阵，等等。Scaling问题的情况(I)和(Ii)及其应用已经研究了很长时间，问题的情况(Iii)包括确定矩阵对策的遍历值问题，情况(Iv)是线性规划的自然推广。本研究的重点是研究各种Scaling问题的计算复杂性，以及开发有效的算法和近似方案，并对算法进行计算测试。

This project will investigate the algorithmic aspects of matrix scaling problems. These problems call for pre and post multiplication of a given matrix by two diagonal matrices so that the resulting scaled matrix satisfies prescribed conditions. A wide variety of practical and theoretical problems fall within the general framework of matrix scaling problems. These include: (i) scaling of nonnegative matrices to prescribed row-column sums, (ii) similarity scaling, balancing, and matrix preconditioning, (iii) scaling of nonnegative matrices to prescribed row-column maxima-minima, (iv) scaling of positive semidefinite matrices, and some others. Cases (i) and (ii) of the scaling problem and their applications have been studied for a long time, case (iii) of the problem includes the problem of determining the ergodic values of matrix games, and case (iv) turn out to be a natrual generalization of linear programming. The emphasis of this research is the study of the computational complexity of various types of scaling problems, as well as the development of effective algorithms and approximation schemes, and to test the algorithms computationally.