正定値対称行列$A\in {\mathbb R}^{N\times N}$を下三角行列$R\in {\mathbb R}^{N\times N}$を用いて$RR^\top$と書くことを、$A$をCholesky分解するといいます。以下の手順をふみます。
$$ A_{j,i}=\sum_{h=1}^NR_{j,h}R_{i,h}$$という関係式があるので、最初$R=O$(零行列)とし、第$i-1$列まで$R$の値が確定したとして、
1. $R_{i,i}=\sqrt{A_{i,i}-\sum_{h=1}^{i-1}R_{i,h}^2}$
2. $j=i+1,\ldots,N$に対して、$R_{j,i}=(A_{j,i}-\sum_{h=1}^{i-1}R_{j,h}R_{i,h})/R_{i,i}$
によって第$i$列の$i+1$行目以降を設定します。この操作を$i=1,\ldots,N$に対して行います。

そして、$R$の第$r+1$列以降を0とおいた台形の形をした$\tilde{R}$を用いて$A\approx \tilde{R}\tilde{R}^\top$というように(階数$r$に)近似することを$A$を不完全Cholesky分解するといいます。ただ、上記の手順を途中の$r$列目までで止めるだけでは芸がありません。近似の精度が良くなるように工夫します。

まず、最初に$B:=A$とし、上記の手順を以下のように修正します。$$B_{j,i}=\sum_{h=1}^NR_{j,h}R_{i,h}$$という関係式があるので、最初$R=O$とし、第$i-1$列まで$R$の値が確定したとして、$R_{k,k}=\sqrt{B_{k,k}-\sum_{h=1}^{i-1}R_{k,h}^2}$ ($i\leq k\leq N$)を最大にする$k$について、$B$の$i,k$行と$i,k$列、$R$の$i,k$行をいれかえます。その上で、$j=i+1,\ldots,N$に対して、$R_{j,i}=(B_{j,i}-\sum_{h=1}^{i-1}R_{j,h}R_{i,h})/R_{i,i}$によって第$i$列の$i+1$行目以降を設定します。また、大きさ$N$の単位行列で、$Q_i(i,k)=Q_{i}(k,i)=1$, $Q_i(i,i)=Q_{i}(k,k)=0$とした行列$Q_i$を設定します。そのようにして、$r$列目まですすめ、$P:=Q_{1}\cdots Q_r$を用いて以下のようにできます。$$A= PBP^\top\approx P\tilde{R}\tilde{R}^\top P^\top$$

このようにすると、誤差$B-\tilde{R} \tilde{R}^\top$をそのトレースで評価するとして、実行終了時の$\sum_{i=r+1}^NR_{i,i}^2$に等しくなります。実際、$r+1\leq i\leq N$について、$R^\top R$の$(i,i)$成分が$\sum_{j=1}^r R_{i,j}^2$となり、これと$B_{i,i}$との差が$R_{i,i}^2$となります。つまり、$R_{i,i}^2$の値の大きな$i$から順に選択していきます。事前に用意した$r$を用いて$r$列で止めてもよいし、$R_{i,i}^2$が事前に用意したある値にしてもよいと思います。また、上記の手順でいくと、$R^2_{i,i}$が単調減少になることが保証されます。実際、$R_{k,k}^2=B_{k,k}-\sum_{h=1}^{i-1}R_{k,h}^2$が第$i$列として選択されない($R^2_{i,i}より小さい)$と、$i+1$列目では、$R_{k,k}^2=B_{k,k}-\sum_{h=1}^{i}R_{k,h}^2$となって、さらに$R_{k,i}^2$だけ小さくなります。