# Symbolic Cholesky decomposition

{{ safesubst:#invoke:Unsubst||$N=Unreferenced |date=__DATE__ |$B= {{#invoke:Message box|ambox}} }} In the mathematical subfield of numerical analysis the symbolic Cholesky decomposition is an algorithm used to determine the non-zero pattern for the ${\displaystyle L}$ factors of a symmetric sparse matrix when applying the Cholesky decomposition or variants.
Let ${\displaystyle A=(a_{ij})\in \mathbb {K} ^{n\times n}}$ be a sparse symmetric positive definite matrix with elements from a field ${\displaystyle \mathbb {K} }$, which we wish to factorize as ${\displaystyle A=LL^{T}\,}$.
The following algorithm gives an efficient symbolic factorization of ${\displaystyle A\,}$ :
{\displaystyle {\begin{aligned}&\pi (i):=0~{\mbox{for all}}~i\\&{\mbox{For}}~i:=1~{\mbox{to}}~n\\&\qquad {\mathcal {L}}_{i}:={\mathcal {A}}_{i}\\&\qquad {\mbox{For all}}~j~{\mbox{such that}}~\pi (j)=i\\&\qquad \qquad {\mathcal {L}}_{i}:=({\mathcal {L}}_{i}\cup {\mathcal {L}}_{j})\setminus \{j\}\\&\qquad \pi (i):=\min({\mathcal {L}}_{i}\setminus \{i\})\end{aligned}}}