Software Lab: Parallel Graph Algorithms

We run through the main stages of a typical software development process inspired by practically relevant graph algorithms.

General Information

... on the administrative structure of the lab can be found here.

Groups

Topics

  1. graph coloring for direct Jacobian and Hessian compression; see A. Gebremedhin et al.: What Color is your Jacobian? SIAM, 2005 and Jun 15 and Jul 20 lectures of SS21 course on Combinatorial Problems in Scientific Computing (CPSC)
  2. nested dissection for symbolic Gauss and Cholesky factorizations by vertex elimination applied to adjacency graphs; see L. Grigori et al.: Hypergraph-Based Unsymmetric Nested Dissection Ordering for Sparse LU Factorization. SIAM, 2010 and Jul 6 lecture of SS21 course on CPSC

User Requirements

Topic 1. (Graph Coloring for Jacobian and Hessian Compression)

In Algorithmic Differentiation direct methods for computing compressed Jacobian and Hessian matrices are based on colorings of various graphs (row/column incidence graphs, bipartite graph, adjacency graph) derived from the sparsity patterns of the given Jacobians and/or Hessians. The number of colors required determines the degree of compression; less colors yields higher compression. Coloring graphs with a minimal number of colors is NP-complete. Sequential Coloring based on various vertex orderings is a popular heuristic.

Develop a parallel Sequential Coloring software library for the various use cases and test it with graphs derived from the SuiteSparse Matrix Collection. The software must run on the RWTH Compute Cluster as well as on a normal PC.

Topic 2. (Nested Dissection for Matrix Factorization)

In Numerical Linear Algebra direct methods for solving systems of linear equations rely on factorization (e.g. Gauss or Cholesky) of the system matrix. Sparse factorization suffers from potential fill-in (zero entries are turned into nonzeros). Fill-in needs to be predicted and minimized in order to avoid inefficient dynamic memory management. Minimization of Fill-in is NP-complete. Nested Dissection is a popular heuristic.

Develop a parallel Nested Dissection software library for directed and undirected graphs and test it with graphs derived from the SuiteSparse Matrix Collection. The software must run on the RWTH Compute Cluster as well as on a normal PC.

Test Problems

See SuiteSparse Matrix Collection; transformation of sparse matrices into the relevant graphs is part of the system requirements.

Agenda

  • Kick-off meeting on Jul 16, 2024, 10am in Seminarraum 231, IT Center, Seffenter Weg 23
  • Proposal (PDF slides to info@stce.rwth-aachen.de) by Oct 6, 2024. Presentation on Oct 11, 2024, 10am in Seminarraum 231
  • Requirements (slides) by Nov 7, 2024. Presentation on Nov 8, 2024, 10am in Seminarraum 231.
  • Design (slides) by Dec 12, 2024. Presentation on Dec 13, 2024, 10am in  Seminarraum 231.
  • Implementation (slides; access to source repository on git.rwth-aachen.de) by Jan 9, 2025. Presentation on Jan 10, 2025, 10am in Seminarraum 231 .
  • Final Presentation on Jan 24, 2025, 10am in Seminarraum 231.
  • Publication (PDF report) by Jan 31, 2025.