Add support for 1-coloring instead of only 2-coloring

Issue #25 resolved
Jed Brown
created an issue

MatGetColoring() computes a coloring of A^T A, which is a 2-coloring of the graph A. Support for a 1-coloring would also be useful.

Comments (8)

  1. Peter Brune

    Colpack appears to have OpenMP support but not MPI. Would it really be enough of an improvement on what we have now to need adding an actual interface and externalpackage? Stefano, what's your experience here?

  2. Stefano Zampini

    I gave Colpack a try for its different coloring options. No efficiency reasons: the graph I had to color was a face-centered adjacency graph of subdomains connectivity, so very few vertices and edges. With very regular domains (cubes) in 3D and such a graph, Colpack returns a coloring with 18-20 colors which is almost the optimal number of colors (18).

    Instead, what about Boost? Have you ever tried it?

  3. Peter Brune

    The group who publishes the most on this stuff put their distributed memory implementations of distance 1 and 2 matrix coloring into Zoltan. I've updated the externalpackage to the latest version in a branch, and am now wrapping it.

    I've got my own implementations, but they're probably not as well tested yet.

  4. Peter Brune

    An update; the Zoltan coloring algorithms take the passed-in communicator for some sort of wild ride that through some nasty set of duplications and reduplications breaks our reference counting. I've tried to trace it and fix it and it's pretty deep in their code way away from the coloring algorithms where it happens and doesn't happen for a good reason.

    Some good news, however, is that I've been able to test -mat_coloring_type greedy and (the slower but general-distance) -mat_coloring_type jp for distance 1 and distance 2 coloring. These are ready for testing and open for feature or interface suggestions if need be.

  5. Log in to comment