|
|
Incomplete Cholesky FactorizationAuthor: Austen Duffy, Florida State University An incomplete Cholesky (IC) factorization can be used as a preconditioning matrix for the conjugate gradient algorithm, and is often the best choice if the matrix a is large, sparse (many 0 entries) and symmetric-positive definite (A=A^T, x^TAx > 0). The IC factorization essentially just ignores the 0 entries of the matrix A and thus the preconditioner matrix M is able to maintain A's sparse structure. One can use the form M=LL^T where the lower triangular matrix L stores the square root of the diagonal of A, or one can use the root free form M=LDL^T where D stores the diagonal of A and L has 1 diagonal. Below we give a simple Fortran subroutine for computing the M=LL^T form, for more information on this version there is an excellent book which provides this algorithm "Matrix Computations" by Golub and van Loan. For a parallel version, one can use the M=LDL^T version with a red black ordering and the algorithm provided in Ortega's book "Introduction to Parallel and Vector Solution of Linear Systems".
|
|