0
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$
    – TiantianHe
    Dec 21, 2021 at 7:23
  • $\begingroup$ @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. $\endgroup$
    – Anton Menshov
    Dec 21, 2021 at 7:32
  • $\begingroup$ Thanks for your help,Can you give me some papers about drop tolerance-based incomplete Cholesky decomposition $\endgroup$
    – TiantianHe
    Dec 21, 2021 at 8:08
  • $\begingroup$ @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. $\endgroup$
    – Anton Menshov
    Dec 21, 2021 at 8:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.