Module graph_coloring 

Distance-2 graph coloring for parallel ILU/IC.

Colors vertices of the adjacency graph of a sparse matrix such that no two vertices within distance 2 share the same color. This enables parallel processing of independent rows during ILU(0) or IC(0) factorization: all rows with the same color can be processed simultaneously without data races.

Algorithm

Uses a greedy distance-2 coloring:

1. Process rows in order 0, 1, …, n-1.
2. For each row i, collect colors of all distance-1 neighbors (columns in row i) and distance-2 neighbors (columns of the rows of distance-1 neighbors).
3. Assign to row i the smallest color not in the collected set.

This yields an upper bound of Δ^2 + 1 colors where Δ is the maximum degree, which is tight for some graphs but typically much better in practice for sparse matrices from discretized PDEs.

Parallel ILU(0)

After coloring, ILU(0) proceeds color-by-color: for each color c, all rows with that color can be updated in parallel. Within a color, no row depends on another (guaranteed by the distance-2 property).

Structs

GraphColoring

Result of a distance-2 graph coloring of a sparse matrix.