Uniform Boundedness of a Preconditioned Normal Matrix Used in Interior-Point Methods
研究了内点算法中求解线性方程组时使用的基预处理子，证明当D取所有正对角矩阵时，预处理后的矩阵条件数一致有界，并给出了连通有向图情形下的具体上界。
Solving systems of linear equations with "normal" matrices of the form AD2AT is a key ingredient in the computation of search directions for interior-point algorithms. In this article, we establish that a well-known basis preconditioner for such systems of linear equations produces scaled matrices with uniformly bounded condition numbers as D varies over the set of all positive diagonal matrices. In particular, we show that when A is the node--arc incidence matrix of a connected directed graph with one of its rows deleted, then the condition number of the corresponding preconditioned normal matrix is bounded above by m(n - m + 1), where m and n are the number of nodes and arcs of the network.