Symbolic Cholesky decomposition

In the mathematical subfield of numerical analysis the symbolic Cholesky decomposition is an algorithm used to determine the non-zero pattern for the $L$ factors of a symmetric sparse matrix when applying the Cholesky decomposition or variants.

Algorithm

Let:$A=(a\_\{\; u,mu\})\; in\; mathbb\{K\}^\{n\; imes\; n\}$

be a sparse symmetric positive definite matrix, which we wish to factorize as:$A\; =\; LL^T,$

In order to implement an efficient sparse factorization it has been found to be necessary to determine the non zero structure of the factors before doing any numerical work.

Let $mathcal\{A\}\_i$ and $mathcal\{L\}\_j$ be sets representing the non-zero patterns of columns i and j (below the diagonal only) of matrices A and L respectively.

Take $minmathcal\{L\}\_j$ to mean the least element of $mathcal\{L\}\_j$.

Define the elimination tree on the matrix by use of a parent function $pi(i),!$.

Then the following algorithm will give an efficient symbolic factorization of $A,$

:$mbox\{For\}~i=1,\; n$::$mathcal\{L\}\_i\; =\; mathcal\{A\}\_i$::$mbox\{For\}~j~mbox\{such\; that\}~pi(j)\; =\; i$:::$mathcal\{L\}\_i\; =\; mathcal\{L\}\_i\; cup\; mathcal\{L\}\_jsetminus\{j\}$::$pi(i)\; =\; minmathcal\{L\}\_isetminus\{i\}$