# Conjugate gradient with incomplete Cholesky preconditioner

**URL:** <https://discourse.julialang.org/t/conjugate-gradient-with-incomplete-cholesky-preconditioner/7809>\
**Category:** Numerics\
**Created:** [December 17, 2017, 2:10am UTC](https://discourse.julialang.org/t/conjugate-gradient-with-incomplete-cholesky-preconditioner/7809 "2017-12-17T02:10:18Z")\
**Posts on this page:** 3\
**Page:** 2

<div class="post-metadata">

**Author:** ![RoyiAvital](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/royiavital/32/571_2.png) [@RoyiAvital](https://discourse.julialang.org/u/RoyiAvital)\
**Post date:** [September 6, 2021, 9:15pm UTC](https://discourse.julialang.org/t/conjugate-gradient-with-incomplete-cholesky-preconditioner/7809/21 "2021-09-06T21:15:54Z")

</div>

It seems I wasn’t clear.  
In option (3), the way I get it, one could select arbitrary number. Since the documentation mentioned the memory is multiplied by the `nnz` I though it means it is (2).

Anyhow, what about the diagonal modification? It is not mentioned on documentation but code does mention something like it.

---

<div class="post-metadata">

**Author:** ![dpo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpo/32/3335_2.png) [@dpo](https://discourse.julialang.org/u/dpo)\
**Post date:** [September 6, 2021, 9:48pm UTC](https://discourse.julialang.org/t/conjugate-gradient-with-incomplete-cholesky-preconditioner/7809/22 "2021-09-06T21:48:01Z")

</div>

Like I said, and as explained in the docstring, the total amount of memory is nnz(A) + p \* n, where n is the matrix size. It’s not an arbitrary number, but it can be controled to some degree. I don’t know if that’s also what Matlab does.

The same docstring also mentions diagonal shift:

> - `α::Tv=Tv(0)` : initial value of the shift in case the incomplete LDLᵀ factorization of `A` is found to not exist. The shift will be gradually increased from this initial value until success.

The feature that’s not properly documented is that a negative shift is introduced at diagonal places where `A[i,i] ≤ 0` to perform limited-memory SQD factorizations.

---

<div class="post-metadata">

**Author:** ![RoyiAvital](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/royiavital/32/571_2.png) [@RoyiAvital](https://discourse.julialang.org/u/RoyiAvital)\
**Post date:** [September 6, 2021, 10:27pm UTC](https://discourse.julialang.org/t/conjugate-gradient-with-incomplete-cholesky-preconditioner/7809/23 "2021-09-06T22:27:13Z")

</div>

I am not talking about the diagonal shift. I am talking about what is called modified incomplete Cholesky factorization:

 ![image](https://global.discourse-cdn.com/julialang/original/3X/b/3/b3ac38a0c394c429eebea25d541887888b201de7.png)

This is taken from Yousef Saad - Iterative Methods for Sparse Linear Systems (2nd Edition):

 ![image](https://global.discourse-cdn.com/julialang/original/3X/4/a/4af4dda3431ab0c00cb8e522edc8c5c1d061522a.png)

MATLAB’s `ichol()` borrows this trick from `ILU` into `IC`. I think the reference you use has done it as well (At least links to it).

Assume I understand all the documentation you have written. I am not talking about shifting, I am talking about diagonal compensation which improves the conditioning.

By the way, (3) means the user can chose arbitrary number of elements. If the user selected 5, the decomposition will leave the 5 largest components.  
In (2) it means the memory allocation is a multiplication of the number of elements of the matrix to start with (As it saves components within `l` steps from the given structure).

From documentation I don’t understand what’s the policy you have. Also if the algorithm is (3) why are the memory allocations a multiplication of `n`?

[Previous page](https://discourse.julialang.org/t/conjugate-gradient-with-incomplete-cholesky-preconditioner/7809.md?page=1)