Science Fair Project Encyclopedia
Symbolic Cholesky decomposition
In the mathematical subfield of numerical analysis the symbolic Cholesky decomposition is an algorithm used estimate the worst possible fill-in for a symmetric sparse matrix when applying the Cholesky decomposition.
be a symmetric positive definite matrix. Before doing a Cholesky decomposition of A into L and L*, we want to calculate the worst possible fill-in F:=L + L* that can happen during the actual Cholesky decomposition.
- GA = (VA,EA)
- GF: = (VA,EF)
is the graph for the matrix F.
To construct EF first set EF := EA then
for i=1,...,m-1 we construct
- Gi := remove the vertex i from the graph Gi-1 and all edges incident to i
- add new edges to Gi so that all vertices that were adjacent to i now form a clique
- add the new edges added to Gi to EF
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details