Chordal.jl

Author tjdiamandis
Popularity
7 Stars
Updated Last
6 Months Ago
Started In
February 2021

ChordalDecomp

Build Status Coverage

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

  1. 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 Duff. 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
  2. Symbolic Cholesky factorization
    • This provides the chordal extension (get edge set E from L)
  3. Merge cliques into larger blocks
    • form clique graph or tree
    • choose heuristic merging algorithm
  4. Index selector matrices

Clique Merging Strategies

Clique Tree Based (Vandenberghe paper)

  1. 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
  2. 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

Clique Graph based (Garstka et al., implemented in COSMO.jl)

  1. 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
  2. Algorithm (greedy):
    1. Merge cliques connected by edge with highest positive weight
    2. Recompute weights
    3. If there are more positive weights, repeat. Else, break.

References