CRPC-TR97771						November 1997

Title: A New Class of Preconditioners for Large-Scale Linear Systems from 
Interior Point Methods for Linear Programming

Author: A.R.L. Oliveira and D.C. Sorensen

Submitted September 1998; Available as Rice CAAM TR97-27; In review for 
SIAM J. Optimization

Abstract:
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 
experiements 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.

Key words: linear programming, interior-point methods, preconditioners, 
augmented system

AMS subject classifications: 65F50, 90C05, 90C06

Abbreviated Title: Preconditioners for Interior Point Methods

------------------------------------------------------------------------------
A.R.L. Oliveira				D.C. Sorensen
aurelio@densis.fee.unicamp.br		sorensen@caam.rice.edu
State University of Campinas UNICAMP	Department of Computational and 
						Applied Mathematics
					Rice University