Semi-sparse Cholesky Factorization
Author: Ivan Šimeček
High-performance, sparse matrices, numerical algebra, Cholesky
<>The Cholesky factorization (shortly
is one of basic methods to solve systems of linear equations (shortly
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
different right hand sides.
A matrix A is considered as dense
if it contains about n2 nonzero elements and it is sparse
In practice, a matrix is considered sparse if the ratio of nonzero
drops bellow 10%.
If a sparse matrix has the nonzero elements
occurring only around the main diagonal, it is banded.
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
elements, called fills (or fill-in’s). For the minimal
fills, special process called symbolic factorization is needed.
this process significantly increases the number of required operations,
computation of the CHF for sparse matrices is a still open research
final version (in .DOC format)
author = "I.
title = "Semi-sparse
journal = "CTU Workshop",
volume = "9",
pages = "184-185",
month = mar,
year = "2005",
Address = "Prague, Czech Republic"