CRPC-TR97772						November 1997

Title: Computational Experience with a Preconditioner for Interior Point 
Methods for Linear Programming

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

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

Abstract:
In this paper, we discuss efficient implementation of a new class of 
preconditioners for linear systems arising from interior point methods. 
These new preconditioners give superior performance near the solution of 
a linear programming problem where the linear systems are typically 
highly ill-conditioned. They rely upon the computation of an LU 
factorization of a subset of columns of the matrix of constraints. The 
implementation of these new techniques require some sophistication since 
the subset of selected columns is not known a priori. The conjugate 
gradient method using this new preconditioner compares favorably with the 
Cholesky factorization approach. The new approach is clearly superior for 
large scale problems where the Cholesky factorization produces 
intractable fill-in. Numerical experiements on several representative 
classes of linear programming problems are presented to demonstrate the 
promise of the new preconditioner.

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

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

Abbreviated Title: Computational Experience with a Preconditioner

------------------------------------------------------------------------------
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