A new class of preconditioners for large-scale linear systems from interior point methods for linear programming

A new class of preconditioners for the iterative solution of the linear systems arising from interior point methods is proposed. For many of these methods, the linear systems are symmetric and indefinite. The system can be reduced to a system of normal equations which is positive definite. We show that all preconditioners for the normal equations system have an equivalent for the augmented system while the opposite is not true. The new class of preconditioners works better near a solution of the linear programming problem when the matrices are highly ill conditioned. The preconditioned system can be reduced to a positive definite one. The techniques developed for a competitive implementation are rather sophisticated since the subset of columns is not known a priori. The new preconditioner applied to the conjugate gradient method compares favorably with the Cholesky factorization approach on large-scale problems whose Cholesky factorization contains too many nonzero entries. (C) 2004 Elsevier Inc. All rights reserved.