Supriya Ghosh (Editor)

Symbolic Cholesky decomposition

Updated on
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit
Covid-19

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 i j ) K n × n be a sparse symmetric positive definite matrix with elements from a field K , which we wish to factorize as A = L L 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. To write the algorithm down we use the following notation:

  • Let A i and L j be sets representing the non-zero patterns of columns i and j (below the diagonal only, and including diagonal elements) of matrices A and L respectively.
  • Take min L j to mean the smallest element of L j .
  • Use a parent function π ( i ) to define the elimination tree within the matrix.
  • The following algorithm gives an efficient symbolic factorization of A :

    π ( i ) := 0   for all   i For   i := 1   to   n L i := A i For all   j   such that   π ( j ) = i L i := ( L i L j ) { j } π ( i ) := min ( L i { i } )

    References

    Symbolic Cholesky decomposition Wikipedia


    Similar Topics
    Kaagaz Ke Phool
    Jim Bowen
    Eva Pölzing
    Topics
     
    B
    i
    Link
    H2
    L