Version 1.0.1

16th April 2013

Recent Changes

Code Download

  • Single
  • Double

HSL_MI27 Projected preconditioned conjugate gradient method for saddle-point systems

This package uses the projected preconditioned conjugate gradient method to solve (n + m) × (n + m) saddle-point systems of the form

A BT B C x y = C d ,

where A is an n × n real and symmetric matrix, C is an m × m real, symmetric and positive semi-definite (possibly zero) matrix, and m n. A preconditioner of the form

P = G BT B C

must be available where G is a real and symmetric matrix. The following assumptions are assumed to hold:

If these assumptions do not hold, then negative curvature may occur and, consequently, the method terminates with an error.

The projected preconditioned conjugate gradient method iteratively finds the vector x and then, once x has been computed to a high enough level of accuracy, the vector y is computed by performing one additional solve with the preconditioner P. Reverse communication is used for preconditioning and matrix-vector products of the form As, Bs, BTs and Cs. HSL_MI13 may be used to efficiently form suitable preconditioners and carry out the required preconditioning solves; HSL_MC65 may be used to form the required matrix-vector products. HSL_MI13 and HSL_MC65 are both available as part of the current version of HSL.