STFC Website

part of UK Research & Innovation

Version 1.2.0

22nd March 2010

MI11: Unsymmetric system: incomplete LU factorization

This routine forms an incomplete \(\mathbf{LU}\) factorization of an \(n \times n\) sparse unsymmetric matrix \(\mathbf{A}\). No fill-in is allowed. The entries of \(\mathbf{A}\) are stored by rows. If \(\mathbf{A}\) has zeros on the diagonal, the routine first finds a row permutation \(\mathbf{Q}\) which makes the matrix have nonzeros on the diagonal. The incomplete \(\mathbf{LU}\) factorization of the permuted matrix \(\mathbf{QA}\) is then formed. \(\mathbf{L}\) is lower triangular and \(\mathbf{U}\) is unit upper triangular. The incomplete factorization may be used as a preconditioner when solving the linear system \(\mathbf{Ax} = \mathbf{b}\). A second entry performs the preconditioning operations

\[\mathbf{y} = \mathbf{P} \mathbf{z} \; \mbox{ and } \; \mathbf{y} = \mathbf{P} ^ T \mathbf{z},\] where \(\mathbf{P} = (\mathbf{LU}) ^{-1} \mathbf{Q}\) is the preconditioner.