# All Science Fair Projects

## Science Fair Project Encyclopedia for Schools!

 Search    Browse    Forum  Coach    Links    Editor    Help    Tell-a-Friend    Encyclopedia    Dictionary

# Science Fair Project Encyclopedia

For information on any area of science that interests you,
enter a keyword (eg. scientific method, molecule, cloud, carbohydrate etc.).
Or else, you can start by choosing any of the categories below.

# 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.

## Algorithm

Let

$\mathbf{A}=(a_{\nu,\mu}) \in \mathbb{K}^{n \times n}$

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.

Let

GA = (VA,EA)

be the undirected graph associated with the matrix A. To simplify the notation we identify the different vertices with integers so that

$V_A:=\lbrace 1,\ldots,m \rbrace$

and

$E_A:=\lbrace(\nu,\mu)\mid a_{\nu,\mu} \ne 0 \rbrace$.

Then

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

1. Gi := remove the vertex i from the graph Gi-1 and all edges incident to i
2. add new edges to Gi so that all vertices that were adjacent to i now form a clique
3. add the new edges added to Gi to EF
03-10-2013 05:06:04