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

Version 1.3.1

2nd April 2015

User documentation

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 = (\begin{matrix} A & B^{T} \\ B & - C \end{matrix}),

where $A$ is $(n - m) \times (n - m)$ symmetric positive deﬁnite, $B$ is rectangular $m \times (n - m)$ and of full rank ( $m < n$ ), and $C$ is $m \times 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}{rcl} \bar{K} = S Q^{T} (\begin{matrix} A & B^{T} \\ B & - C \end{matrix}) Q S + (\begin{matrix} α (1) I & 0 \\ - α (2) I \end{matrix}) \end{array}

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

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

y = P z

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

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

\bar{K} = (L + R) D {(L + R)}^{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 = R D 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.