## Version 1.3.1

2nd April 2015

Recent Changes

Code Download

• Single
• Double

### HSL_MI30 Symmetric indeﬁnite saddle-point system: signed incomplete Cholesky factorization

Let $K$ be a sparse symmetric saddle-point matrix of the form

$K=\left(\begin{array}{cc}\hfill A\hfill & \hfill {B}^{T}\hfill \\ \hfill B\hfill & \hfill -C\hfill \end{array}\right),$

where $A$ is $\left(n-m\right)×\left(n-m\right)$ symmetric positive deﬁnite, $B$ is rectangular $m×\left(n-m\right)$ and of full rank ($m), and $C$ is $m×m$ symmetric positive semi-deﬁnite. HSL_MI30 computes a signed incomplete Cholesky factorization. The matrix $K$ is optionally reordered, scaled and, if necessary, shifted to avoid breakdown of the factorization so that the incomplete factorization of

$\begin{array}{rcll}\stackrel{̄}{K}=S{Q}^{T}\left(\begin{array}{cc}\hfill A\hfill & \hfill {B}^{T}\hfill \\ \hfill B\hfill & \hfill -C\hfill \end{array}\right)QS+\left(\begin{array}{cc}\hfill \alpha \left(1\right)I\hfill & \hfill 0\hfill \\ \hfill \hfill & \hfill -\alpha \left(2\right)I\hfill \end{array}\right)& & & \text{}\end{array}$

is computed, where $Q$ is a permutation matrix, $S$ is a diagonal scaling matrix and $\alpha \left(1:2\right)$ are non-negative shifts.

The incomplete factorization may be used for preconditioning when solving the saddle-point system $Kx=b$. A separate entry performs the preconditioning operation

$y=Pz$

where $P={\left(\overline{L}D{\overline{L}}^{T}\right)}^{-1}$, with $\overline{L}=Q{S}^{-1}L$, is the incomplete signed Cholesky factorization preconditioner. An option exists to use $P={\left(\overline{L}|D|{\overline{L}}^{T}\right)}^{-1}$ as the preconditioner.

The incomplete factorization is based on a matrix decomposition of the form

 $\overline{K}=\left(L+R\right)D{\left(L+R\right)}^{T}-E,$ (1)

where $L$ is lower triangular with unit diagonal entries, $R$ is a strictly lower triangular matrix with small entries that is used to stabilize the factorization process, $D$ is a diagonal matrix, and $E$ has the structure

 $E=RD{R}^{T}+F+{F}^{T},$ (2)

where $F$ is strictly lower triangle. $F$ is discarded while $R$ is used in the computation of $L$ but is then discarded. The user controls the dropping of small entries from $L$ and $R$ and the maximum number of entries within each column of $L$ and $R$ (and thus the amount of memory for $L$ and the intermediate work and memory used in computing the incomplete factorization).

Note: If an incomplete Cholesky factorization preconditioner for a positive-deﬁnite system is required, HSL_MI28 should be used.