STFC Website

part of UK Research & Innovation

Version 1.1.0

20th December 2005

MA61: Sparse symmetric positive-definite system: incomplete factorization

To solve a symmetric, sparse and positive definite set of linear equations \(\mathbf{Ax} = \mathbf{b}\) i.e. \[\sum_ {j=1} ^ n a _{ij}x _j = b _i,\; i=1,2,..., n.\] The solution is found by a preconditioned conjugate gradient technique, where the preconditioning is done by incomplete factorization.

(a) MA61A performs the incomplete factorization based on an \(\mathbf{LDL} ^T\) decomposition. New entries which have small numerical values compared to the corresponding diagonal entries are dropped, and the diagonal entries are modified to ensure positive definiteness. This results in a preconditioning matrix \(\mathbf{C}\) held in \(\mathbf{LDL} ^T\) form.

(b) MA61B performs the iteration procedure using the preconditioned coefficient matrix (i.e. \(\mathbf{AC} ^{-1}\) ) as the iteration matrix for the conjugate gradient algorithm.