Solving systems of linear equations with “normal” matrices of the form $A D^2 A^T$ 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.
Citation
Manuscript, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332, March 2003.