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