Coloring

In parallel scientific computing applications, computational dependency is often modeled using a graph. A vertex coloring of the graph is then used as a routine to identify independent subtasks that can be performed concurrently. Examples of cases where coloring is used for such a purpose include iterative solution of sparse linear systems, preconditioners, sparse tiling, and eigenvalue computation. The computational (model) graph in such contexts is often already distributed among processors and therefore the coloring needs to be performed in parallel. The alternative approach of gathering the graph on one processor for a subsequent sequential coloring (by the same processor) is prohibitively time consuming or even infeasible due to memory constraints.

We designed and developed a scalable shared- and distributed-memory parallel distance-1 and distance-2 coloring algorithms. A (distance-1) coloring of a graph is an assignment of positive integers (colors) to vertices such that every pair of adjacent vertices receives different colors. The distance-2 graph coloring problem aims at partitioning the vertex set of a graph into the fewest sets consisting of vertices pairwise at distance greater than two from each other.

Equivalence among structurally orthogonal column partition of a matrix \(A\), distance-2 coloring of the graph \(G(A)\) of \(A\) and distance-1 coloring of \(G^{2}(A)\). Top: symmetric case. Bottom: non-symmetric case, where \(G_{b}^2[V_2]\) denotes the subgraph of the square graph \(G_{b}^{2}\) induced by the vertex set \(V_2\).

Implementation of our algorithms can be found as part of Zoltan at the Zoltan project web site.

Related Publications