STFC Website

part of UK Research & Innovation

Version 1.1.0

1st March 2023

HSL_MI27: Projected preconditioned conjugate gradient method for saddle-point systems

This package uses the projected preconditioned conjugate gradient method to solve \((n+m)\times (n+m)\) saddle-point systems of the form \[\left[ \begin{array}{cc} \mathbf{A} & \mathbf{B}^T \\ \mathbf{B} & -\mathbf{C} \end{array} \right] \left[ \begin{array}{c} \mathbf{x}\\\mathbf{y} \end{array} \right] = \left[ \begin{array}{c} \mathbf{C} \\ \mathbf{d} \end{array} \right],\] where \(\mathbf{A}\) is an \(n\times n\) real and symmetric matrix, \(\mathbf{C}\) is an \(m\times m\) real, symmetric and positive semi-definite (possibly zero) matrix, and \(m\leq n.\) A preconditioner of the form \[\mathbf{P} = \left[ \begin{array}{cc} \mathbf{G} & \mathbf{B}^T \\ \mathbf{B} & -\mathbf{C} \end{array} \right]\] must be available where \(\mathbf{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 \(\mathbf{x}\) and then, once \(\mathbf{x}\) has been computed to a high enough level of accuracy, the vector \(\mathbf{y}\) is computed by performing one additional solve with the preconditioner \(\mathbf{P}.\) Reverse communication is used for preconditioning and matrix-vector products of the form \(\mathbf{A s},\) \(\mathbf{B s},\) \(\mathbf{B^{\mathit{T}} s}\) and \(\mathbf{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.