Exploiting hyper-sparsity when computing preconditioners for conjugate gradients in interior point methods

Contributed talk at the Dundee Numerical Analysis Conference: 27th June 2007

J. A. J. Hall, Ghussoun Al-Jeiroudi and Jacek Gondzio

Abstract

When using preconditioned conjugate gradients to solve the augmented system in interior point methods, the preconditioner devised by Al-Jeiroudi, Gondzio and Hall requires the identification of a full rank square submatrix B of the constraint matrix analogous to the basis matrix in the revised simplex method. For problems where preconditioned conjugate gradients is a competitive alternative to direct methods, it is critically important that hyper-sparsity is exploited when identifying B. This talk will highlight the huge computational savings that are achieved when hyper-sparsity is exploited and indicate how the techniques can be extended to the more general problem of matrix rank identification.