# Incomplete Cholesky factorization

(Difference between revisions)
 Revision as of 07:20, 14 September 2005 (view source)Zxaar (Talk | contribs)← Older edit Revision as of 12:32, 14 September 2005 (view source)Zxaar (Talk | contribs) Newer edit → Line 10: Line 10: === Algorithm for full matrix ''A'' === === Algorithm for full matrix ''A'' === + We have by definition We have by definition [itex] [itex] Line 16: Line 17: From this we can easily obtain
From this we can easily obtain
+ ---- '''for := 1 step 1 until N do'''
'''for := 1 step 1 until N do'''
Line 27: Line 29: '''end (i-loop)'''
'''end (i-loop)'''
+ ----

## Cholesky Factorization

When the square matrix A is symmetric and positive definite then it has an efficient triangular decomposition. Symmetric means that aij = aji for i,j = 1, ... , N. While positive definite means that

$v \bullet A \bullet v > 0$ $\forall v$

In cholesky factorization we construct a lower triangular matrix L whose transpose LT can itself serve as upper triangular part.
In other words we have
L $\bullet$LT = A

### Algorithm for full matrix A

We have by definition $L_{ij}^T = L_{ji}$
From this we can easily obtain

for := 1 step 1 until N do

$L_{ii} = \left( {a_{ii} - \sum\limits_{k = 1}^{i - 1} {L_{ik}^2 } } \right)^{{1 \over 2}}$
and
$L_{ji} = {1 \over {L_{ii} }}\left( {a_{ij} - \sum\limits_{k = 1}^{i - 1} {L_{ik} L_{jk} } } \right)$ ; where j = i+1, i+2, ..., N

end (i-loop)