ČVUT WORKSHOP'05

Semi-sparse Cholesky Factorization
Author: Ivan Šimeček
Keywords

High-performance, sparse matrices, numerical algebra, Cholesky factorization.


Abstract

<>The Cholesky factorization (shortly CHF) is one of basic methods to solve systems of linear equations (shortly SLEs). A task of the CHF is to compute the matrix L, such that A=LLT. The big advantage of this method is that is possible to solve a set of SLEs with the same matrix A, but with different right hand sides.

A matrix A is considered as dense if it contains about n2 nonzero elements and it is sparse otherwise. In practice, a matrix is considered sparse if the ratio of nonzero elements drops bellow 10%.

If a sparse matrix has the nonzero elements occurring only around the main diagonal, it is banded. Banded-like matrices with some "peaks" are called near banded.

The process of Cholesky factorization of the originally sparse matrix A leads to the matrix L with new nonzero elements, called fills (or fill-in’s). For the minimal number of fills, special process called symbolic factorization is needed. Since this process significantly increases the number of required operations, the efficient computation of the CHF for sparse matrices is a still open research problem 

Download:
final version (in .DOC format)

BibTex entry:
@inproceedings{JA_WOR_CHF,
  author =       "I. \v{S}ime\v{c}ek",
  title =        "Semi-sparse Cholesky Factorization",
  journal =      "CTU Workshop",
  volume =       "9",
  pages =        "184-185",
  month =        mar,
  year =         "2005",
  isbn =         "80-01-03201-9",
  Address =      "Prague, Czech Republic"
}

BACK