Monteiro, Renato D. C.; O’Neal, Jerome W.; Tsuchiya, Takashi Uniform boundedness of a preconditioned normal matrix used in interior-point methods. (English) Zbl 1075.65085 SIAM J. Optim. 15, No. 1, 96-100 (2004). Summary: Solving systems of linear equations with “normal” matrices of the form \(A D^2A^{T}\) is a key ingredient in the computation of search directions for interior-point algorithms. We establish 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. Cited in 2 ReviewsCited in 7 Documents MSC: 65K05 Numerical mathematical programming methods 65F35 Numerical computation of matrix norms, conditioning, scaling 90C05 Linear programming 90C35 Programming involving graphs or networks 90C51 Interior-point methods Keywords:linear programming; interior-point methods; polynomial bound; network flow problems; condition number; preconditioning; iterative methods; normal matrix; node-arc incidence matrix; connected directed graph PDFBibTeX XMLCite \textit{R. D. C. Monteiro} et al., SIAM J. Optim. 15, No. 1, 96--100 (2004; Zbl 1075.65085) Full Text: DOI