HSL_MI13: Preconditioners for saddle-point systems

Given a block symmetric matrix \[\boldsymbol K_{H} = \begin{pmatrix} \boldsymbol H & \boldsymbol A^T \\ \boldsymbol A & - \boldsymbol C \end{pmatrix},\] where \(\boldsymbol H\) has \(n\) rows and columns and \(\boldsymbol A\) has \(m\) rows and \(n\) columns, this package constructs preconditioners of the form \[\boldsymbol K_{G} = \begin{pmatrix} \boldsymbol G & \boldsymbol A^T \\ \boldsymbol A & - \boldsymbol C \end{pmatrix}.\] Here, the leading block matrix \(\boldsymbol G\) is a suitably chosen approximation to \(\boldsymbol H\); it may either be prescribed explicitly, in which case a symmetric indefinite factorization of \(\boldsymbol K_{G}\) will be formed using HSL_MA57, or implicitly. In the latter case, \(\boldsymbol K_{G}\) will be ordered to the form \[\boldsymbol K_{G} = \boldsymbol P \begin{pmatrix} \boldsymbol G_{11}^{} & \boldsymbol G_{21}^T & \boldsymbol A_1^T \\ \boldsymbol G_{21}^{} & \boldsymbol G_{22}^{} & \boldsymbol A_2^T \\ \boldsymbol A_{1}^{} & \boldsymbol A_{2}^{} & - \boldsymbol C \end{pmatrix} \boldsymbol P^T\] where \(\boldsymbol P\) is a permutation and \(\boldsymbol A_1\) is an invertible sub-block (“basis”) of the columns of \(\boldsymbol A\); the selection and factorization of \(\boldsymbol A_1\) uses HSL_MA48 — any dependent rows in \(\boldsymbol A\) are removed at this stage. Once the preconditioner has been constructed, solutions to the preconditioning system \[\begin{pmatrix} \boldsymbol G & \boldsymbol A^T \\ \boldsymbol A & - \boldsymbol C \end{pmatrix} \begin{pmatrix} \boldsymbol x \\ \boldsymbol y \end{pmatrix} = \begin{pmatrix} \boldsymbol a \\ \boldsymbol b \end{pmatrix}\] may be computed.

Full advantage is taken of any zero coefficients in the matrices \(\boldsymbol H\), \(\boldsymbol A\) and \(\boldsymbol C\).