Symbolic Cholesky decomposition

From Wikipedia, the free encyclopedia

You have new messages (last change).

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 = LLT

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 π(i).

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

  1. For i= 1, n
    1. \mathcal{L}_i = \mathcal{A}_i
    2. For j such that π(j) = i
      1. \mathcal{L}_i = \mathcal{L}_i \cup \mathcal{L}_j\{j}
    3. \pi(i) = \min\mathcal{L}_i\{i}
Retrieved from "http://en.wikipedia.org../../../s/y/m/Symbolic_Cholesky_decomposition_5959.html"