Editing Symbolic Cholesky decomposition (section)

==Algorithm==
Let
<math>A=(a_{ij}) \in \mathbb{K}^{n \times n}</math>
be a sparse symmetric positive definite matrix with elements from a field <span style="vertical-align:18%;"><math>\mathbb{K}</math></span>, which we wish to factorize as <math>A = LL^T\,</math>.

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. To write the algorithm down we use the following notation:

*  Let <math>\mathcal{A}_i</math> and <math>\mathcal{L}_j</math> be sets representing the non-zero patterns of columns {{mvar|i}} and {{mvar|j}} (below the diagonal only, and including diagonal elements) of matrices {{mvar|A}} and {{mvar|L}} respectively.
* Take <math>\min\mathcal{L}_j</math> to mean the smallest element of <math>\mathcal{L}_j</math>.
* Use a parent function <math>\pi(i)\,\!</math> to define the elimination tree within the matrix.

The following algorithm gives an efficient 
symbolic factorization of {{mvar|A}} : 

: <math>
\begin{align}
& \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{align}
</math>

{{DEFAULTSORT:Symbolic Cholesky Decomposition}}
[[Category:Articles with example pseudocode]]
[[Category:Matrix decompositions]]