A New Class of Preconditioners for Large-Scale Linear Systems
from Interior Point Methods for Linear Programming
A. R. L. Oliveira and D. C. Sorensen
A new class of preconditioners is proposed for the iterative solution
of linear systems arising from interior point methods. In many cases,
these linear systems are symmetric and indefinite. Typically, these
indefinite systems can be reduced to an equivalent Schur complement
system which is positive definite. We show that all preconditioners
for the Schur complement system have an equivalent for the augmented
system while the opposite is not true. This suggests it may be better
to work with the augmented system. We develop some theoretical
properties of the new preconditioners to support this.
Computationally, we have verified that this class works better near a
solution of the linear programming problem when the linear systems are
highly ill-conditioned. Preliminary experiments which illustrate these
features are presented. The techniques developed for a competitive
implementation are presented in a follow up paper along with numerical
experiments on several classes of linear programming problems.
Technical Report TR97-27, Department of Computational
and Applied Mathematics, Rice University, Houston TX,
November 1997.
Contact: [email protected]