# ChordalDecomp

## TODOs

- Performance and type stability
- Unit tests -- ensure data structure change worked
- PSD matrix completion
- Implement maximal cliques algorithm to avoid LightGraphs dep?
- Implement different pre-cholesky reorderings
- Implement clique tree algorithms
- Allow user-specified weight algorithm for clique graph merging
- Test with larger problems

## Chordal Decomposition Steps

- Reorder the vertex set
`V = {1, 2, ..., n}`

via some heuristics, e.g.,- multi-level nested dissection
- minimum degree
- P. R. Amestoy, T. A. Davis, and I. S Duﬀ. An approximate minimum degree ordering algorithm. SIAM Journal on Matrix Analysis and Applications, 17(4):886905, 1996.

- Can be handled by step 2 below with certain Cholesky implementations

- Symbolic Cholesky factorization
- This provides the
**chordal extension**(get edge set`E`

from`L`

)

- This provides the
- Merge cliques into larger blocks
- form clique graph or tree
- choose heuristic merging algorithm

- Index selector matrices

### Clique Merging Strategies

#### Clique Tree Based (Vandenberghe paper)

- Form the clique tree
**Clique intersection property (CIP):**For each pair of cliques, their intersection is contained in every vertex on the unique path connection them in the tree- Can be efficiently computed from the chordal graph, see:
- Blair, J.R.S., Peyton, B. (1993):An introduction to chordal graphs and clique trees. In: George,A., Gilbert, J.R., Liu, J.W.H. (eds.), Graph Theory and Sparse Matrix Computation. Springer-Verlag, pp 1–29
- Tarjan, R.E., Yannakakis, M. (1984): Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13(3), 566–579
- Lewis, J.G., Peyton, B.W., Pothen, A. (1989): A fast algorithm for reordering sparse matrices for parallel factorization. SIAM J. Sci. Statist. Comput. 10(6), 1146–1173
- https://www.cs.cornell.edu/info/people/csun/papers/cct.ps

- Pick an arbitrary clique as the root. Form a topological ordering (number ea. child before parent) that satisfies the running intersection property to get a perfect elimination ordering

#### Garstka et al., implemented in COSMO.jl)

Clique Graph based (- Create clique graph
- Compute weight function e(C_i, C_j) = w_{ij}
- If eigenvalue is dominant step, can use
`e(Ci, Cj) = |Ci|^3 + |Cj|^3 − |Ci ∪ Cj|^3`

. - See Section 3 of paper

- Algorithm (greedy):
- Merge cliques connected by edge with highest positive weight
- Recompute weights
- If there are more positive weights, repeat. Else, break.

## References

- Lieven Vandenberghe and Martin Andersen's Chordal Graphs and Semidefinite Optimization provides an excellent overview of this area.
- The clique graph implementation follows Garstka et al.. The accompanying solver COSMO.jl has chordal decomposition built-in and several great customization features.