HSL_MI13: Preconditioners for saddle-point systems

Given a block symmetric matrix $${\mathit{K}}_H=\left(\begin{array}{cc}\mathit{H}& {\mathit{A}}^T\\ \mathit{A}& -\mathit{C}\end{array}\right),$$ where $\mathit{H}$ has $n$ rows and columns and $\mathit{A}$ has $m$ rows and $n$ columns, this package constructs preconditioners of the form $${\mathit{K}}_G=\left(\begin{array}{cc}\mathit{G}& {\mathit{A}}^T\\ \mathit{A}& -\mathit{C}\end{array}\right).$$ Here, the leading block matrix $\mathit{G}$ is a suitably chosen approximation to $\mathit{H}$; it may either be prescribed explicitly, in which case a symmetric indefinite factorization of ${\mathit{K}}_G$ will be formed using HSL_MA57, or implicitly. In the latter case, ${\mathit{K}}_G$ will be ordered to the form $${\mathit{K}}_G=\mathit{P}\left(\begin{array}{ccc}{\mathit{G}}_{11}^{}& {\mathit{G}}_{21}^T& {\mathit{A}}_1^T\\ {\mathit{G}}_{21}^{}& {\mathit{G}}_{22}^{}& {\mathit{A}}_2^T\\ {\mathit{A}}_1^{}& {\mathit{A}}_2^{}& -\mathit{C}\end{array}\right){\mathit{P}}^T$$ where $\mathit{P}$ is a permutation and ${\mathit{A}}_1$ is an invertible sub-block (“basis”) of the columns of $\mathit{A}$; the selection and factorization of ${\mathit{A}}_1$ uses HSL_MA48 — any dependent rows in $\mathit{A}$ are removed at this stage. Once the preconditioner has been constructed, solutions to the preconditioning system $$\left(\begin{array}{cc}\mathit{G}& {\mathit{A}}^T\\ \mathit{A}& -\mathit{C}\end{array}\right)\left(\begin{array}{c}\mathit{x}\\ \mathit{y}\end{array}\right)=\left(\begin{array}{c}\mathit{a}\\ \mathit{b}\end{array}\right)$$ may be computed.

Full advantage is taken of any zero coefficients in the matrices $\mathit{H}$, $\mathit{A}$ and $\mathit{C}$.