Č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"
}
