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.
|PDF (with pauses)||Dundee07.pdf|
|PDF (without pauses)||Dundee07_NoPause.pdf|