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

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

G_A = (V_A,E_A)

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

and

.

Then

G_F: = (V_A,E_F)

is the graph for the matrix F.

To construct E_F first set E_F := E_A then

for i=1,...,m-1 we construct

1. G_{i := remove the vertex i from the graph Gi-1 and all edges incident to i}
2. add new edges to G_{i so that all vertices that were adjacent to i now form a clique}
3. add the new edges added to G_{i to EF}