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

(Group i working on topic i)

  1. Kauerauf, Goldschmidt, Kazantzi
  2. Poelma, Grabowski, Glomb
  3. Abazi, Kichler, Szuszies
  4. Delvos, Hökelekli, Hashir

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
  3. nested dissection for Jacobian accumulation by vertex elimination applied to (directed acyclic) computational graphs; see U. Naumann: Optimal accumulation of Jacobian matrices by eliminationmethods on the dual computational graph. Springer, 2004 and May 18 lecture of SS21 course on CPSC
  4. bandwidth reduction (reverse Cuthill-McKee ordering; parallel breadth-first search) for symbolic Gauss and Cholesky factorizations by vertex elimination applied to adjacency graphs; see K. Ueno: Efficient Breadth-First Search on Massively Parallel and Distributed-Memory Machines. Springer, 2017 and Jul 6 lecture of SS21 course on CPSC
  5. bandwidth reduction (reverse Cuthill-McKee ordering; parallel breadth-first search) for direct Jacobian and Hessian compression; see K. Ueno: Efficient Breadth-First Search on Massively Parallel and Distributed-Memory Machines. Springer, 2017 and A. Gebremedhin et al.: What Color is your Jacobian? SIAM, 2005 and Jun 15 and Jul 20 lectures of SS21 course on CPSC (not assigned)

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.

Develop a shared memory parallel 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 offering nodes with up to 48 threads 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 shared memory 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.

Topic 3. (Nested Dissection for Jacobian Accumulation)

In Algorithmic Differentiation the vertex elimination method for computing Jacobians is based on the application of the chain rule of differentiation to the computational (directed acyclic) graph of the given evaluation of the underlying differentiable program. The minimization of the computational cost is NP-complete. Heuristically, the minimization of fill-in generated during vertex elimination can be expected to have a positive impact on the computational efficiency. 

Develop a shared memory parallel  Nested Dissection software library for directed acyclic 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.

Topic 4. (Bandwidth Reduction 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. For matrices with band structure the fill-in is restricted to positions inside the band. Heuristically, the minimization of the bandwidth can be expected to reduce the fill-in. Minimization of bandwidth is NP-complete.

Develop a shared memory parallel Bandwidth minimization software library based on (Reverse) Cuthill-McKee ordering 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.

Topic 5. (Bandwidth Reduction for Jacobian and Hessian Compression)

In Algorithmic Differentiation direct methods for computing compressed Jacobian and Hessian matrices can exploit banded structure of the sparsity patterns of the given Jacobians and/or Hessians. The bandwidth determines the degree of compression; lower bandwidth yields higher compression. Minimization of bandwidth is NP-complete.

Develop a shared memory parallel Bandwidth minimization software library based on (Reverse) Cuthill-McKee ordering for directed  (Jacobians) and undirected (Hessians) 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

  • Welcome Email on 11.7.2022
  • Kick-off meeting on 15.7.2022
  • Proposal (PDF slides to info@stce.rwth-aachen.de) by Oct 9,2022. Presentation on Oct 14, 2022, 8:30am in Seminarraum 004, IT Center, Kopernikusstr.
  • Requirements (slides) by Nov 6, 2022. Presentation on Nov 11, 2022, 8:30am in Seminarraum 004.
  • Design (slides) by Dec 11, 2022. Presentation on Dec 16, 2022, 8:30am in  Seminarraum 004.
  • Implementation (slides; access to source repository on git.rwth-aachen.de) by Jan 8, 2023. Presentation on Jan 13, 2023, 8:30am in Seminarraum 004 .
  • Publication (PDF report) by Feb 2, 2023.
  • Final Presentation on Feb 6, 2023, 8:30am in Seminarraum 004.