Symbolic Cholesky decomposition

From Wikipedia, the free encyclopedia

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.

[edit] Algorithm

Let

A=(a_{\nu,\mu}) \in \mathbb{K}^{n \times 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 \min\mathcal{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}_j\setminus\{j\}
\pi(i) = \min\mathcal{L}_i\setminus\{i\}