Version 1.3.1

2nd April 2015

Recent Changes

Code Download

  • Single
  • Double

HSL_MI30 Symmetric indefinite saddle-point system: signed incomplete Cholesky factorization

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

K = A BT B C ,

where A is (n m) × (n m) symmetric positive definite, B is rectangular m × (n m) and of full rank (m < n), and C is m × m symmetric positive semi-definite. 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

K̄ = SQT A BT B C QS + α(1)I 0 α(2)I

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 Kx = b. A separate entry performs the preconditioning operation

y = Pz

where P = (L¯DL¯T)1, with L¯ = QS1L, is the incomplete signed Cholesky factorization preconditioner. An option exists to use P = (L¯|D|L¯T)1 as the preconditioner.

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

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 = RDRT + F + FT, (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-definite system is required, HSL_MI28 should be used.