Properties and Computational Issues of a Preconditioner for Interior Point Methods

Venansius Baryamureeba and Trond Steihaug

Reports in Informatics No. 180, November 1999, Department of Informatics, University of Bergen, Norway.


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.