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

This package uses the projected preconditioned conjugate gradient method to solve
$\left(n+m\right)\times \left(n+m\right)$
saddle-point systems of the form

$$\left[\begin{array}{cc}\hfill A\hfill & \hfill {B}^{T}\hfill \\ \hfill B\hfill & \hfill -C\hfill \end{array}\right]\left[\begin{array}{c}\hfill x\hfill \\ \hfill y\hfill \end{array}\right]=\left[\begin{array}{c}\hfill C\hfill \\ \hfill d\hfill \end{array}\right],$$
where $A$ is an
$n\times n$ real and
symmetric matrix, $C$
is an $m\times m$
real, symmetric and positive semi-deﬁnite (possibly zero) matrix, and
$m\le n.$ A
preconditioner of the form

$$P=\left[\begin{array}{cc}\hfill G\hfill & \hfill {B}^{T}\hfill \\ \hfill B\hfill & \hfill -C\hfill \end{array}\right]$$
must be available where $G$
is a real and symmetric matrix. The following assumptions are assumed to hold:

- if $C$
is positive deﬁnite, both ${A+B}^{T}{C}^{-1}B$
and ${G+B}^{T}{C}^{-1}B$
are positive deﬁnite;
- if $C=0$
and the columns of the $n\times \left(n-m\right)$
matrix $Z$
span the nullspace of $B,$
both ${Z}^{T}AZ$
and ${Z}^{T}GZ$
are positive deﬁnite;
- if $C={EDE}^{T},$
where $d$
is a $p\times p$
nonsingular matrix with $0<p<m,$
the columns of the $m\times \left(m-p\right)$
matrix $F$
span the nullspace of $C$
and the columns of the $n\times \left(n-m+p\right)$
matrix $Z$
span the nullspace of ${F}^{T}B,$
then both ${Z}^{T}\left({A+B}^{T}{ED}^{-1}{E}^{T}B\right)Z$
and ${Z}^{T}\left({G+B}^{T}{ED}^{-1}{E}^{T}B\right)Z$
are positive deﬁnite.

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 ﬁnds 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,$
${B}^{T}s$ and
$Cs.$
HSL_MI13 may be used to eﬃciently 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.