Properties and Computational Issues of a Preconditioner for
Interior Point Methods
Reports in Informatics No. 180, November 1999, Department of
Informatics, University of Bergen, Norway.
Abstract
This is a collection of four conference proceedings on scientific
computation. In the proceedings, we discuss solving a sequence of
linear systems arising from the application of an interior point
method to a linear programming problem. The sequence of linear
systems is solved by alternating between a direct and an iterative
method. The preconditioner is based on low-rank modifications of the
coefficient matrix where a direct solution technique has been used.
We compare two different techniques of forming the low-rank
modification matrix; namely one by Wang and O'Leary (W. Wang and
D.P. O'Leary, Adaptive use of iterative methods in interior point
methods for linear programming, Computer Science Department
Report CS-TR-3560, Institute for Advanced Computer Studies Report
UMIACS-95-111, University of Maryland, November 1995.) and the other
by Baryamureeba, Steihaug and Zhang (V. Baryamureeba, T. Steihaug and
Y. Zhang, Properties of a class of preconditioners for weighted
least squares problems, Technical Report
No. 170, Department of Informatics, University of Bergen, 5020 Bergen,
Norway, April 30, 1999 (Revised July 6, 1999).). The theory and
numerical testing strongly support the latter. We derive a sparse
algorithm for modifying the Cholesky factors by a low-rank matrix,
discuss the computational issues of this preconditioner, and finally
give numerical results that show the approach of alternating between a
direct and an iterative method to be promising.
Download
Back