# Incomplete Cholesky factorization algorithm

I want to implement incomplete Cholesky factorization to precondition, the algorithm I refer from incomplete Cholesky factorization,

function a = ichol(a)
n = size(a,1);

for k=1:n
a(k,k) = sqrt(a(k,k));
for i=(k+1):n
if (a(i,k)!=0)
a(i,k) = a(i,k)/a(k,k);
endif
endfor
for j=(k+1):n
for i=j:n
if (a(i,j)!=0)
a(i,j) = a(i,j)-a(i,k)*a(j,k);
endif
endfor
endfor
endfor

for i=1:n
for j=i+1:n
a(i,j) = 0;
endfor
endfor
endfunction



but it seems not right.

The problem is the algorithm cannot guarantee that a[k,k] is a positive integer. When a[k,k] is not a positive integer, the algorithm will incur an error.

I want to ask for the correct version of Cholesky decomposition and some relevant references.

Cholesky decomposition is applicable to positive-definite matrices (for positive-semidefinite the decomposition exists, but is not unique). The positive-definiteness, is what ensures that a[k,k] is a positive number and sqrt is ok (see, for example, a Wiki explanation on that).

A similar story is happening with an incomplete Cholesky factorization, as its applicability is also limited to positive-definite matrices.

The fact that you encounter a problem is due to the fact that the matrix you are trying to factorize does not possess the required properties for Cholesky factorizations family (most likely) or the matrix loses its positive-definiteness during the numerical procedure (very unlikely).

Thus, the code above for the incomplete Cholesky factorization is correct.

In your situation, I would suggest looking into, say, incomplete LU factorization, which is a bit heavier but has fewer expectations of the matrices it is applied to. It is a common factorization to be used in many types of preconditioners, which involve matrices that are not positive-definite.

Alternatively, if you can do changes to the matrix you are factorizing (say, you are working on a precondition) that will enforce its positive-definiteness, it may be an even better choice.

• The matrix I used is positive-definite matrices,but the matrix loses its positive-definiteness during the numerical procedure,a[k,k] become a nonnegative number. In some papers point out Incomplete Cholesky is probably the most effective precondition,but it seems not stability enough,the progress will produce a non positive-definite matrices or non semipositive-definite matrices Dec 21, 2021 at 7:23
• @TiantianHe in this case, you might be interested in drop tolerance-based incomplete Cholesky decomposition, but that is a totally different question and its practical applicability varies greatly. Dec 21, 2021 at 7:32
• Thanks for your help,Can you give me some papers about drop tolerance-based incomplete Cholesky decomposition Dec 21, 2021 at 8:08
• @TiantianHe this is the reference I know about it from: sciencedirect.com/topics/computer-science/incomplete-cholesky - but I never used it in practice myself. Dec 21, 2021 at 8:18