## Version 1.0.1

16th April 2013

Recent Changes

• Single
• Double

This package uses the projected preconditioned conjugate gradient method to solve $\left(n+m\right)×\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×n$ real and symmetric matrix, $C$ is an $m×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×\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×p$ nonsingular matrix with $0 the columns of the $m×\left(m-p\right)$ matrix $F$ span the nullspace of $C$ and the columns of the $n×\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.