Tutorial

Here we give a brief introduction to the contents of the package, see the API reference for more details.

using SparseMatrixColorings
using LinearAlgebra
using SparseArrays
using StableRNGs

Coloring problems and algorithms

SparseMatrixColorings.jl is based on the combination of a coloring problem and a coloring algorithm, which will be passed to the coloring function.

The problem defines what you want to solve. It is always a ColoringProblem, and you can select options such as

the structure of the matrix (:nonsymmetric or :symmetric)
the type of partition you want (:column, :row or :bidirectional).

problem = ColoringProblem()

ColoringProblem{:nonsymmetric, :column}()

The algorithm defines how you want to solve it. It can be either a GreedyColoringAlgorithm or a ConstantColoringAlgorithm. For GreedyColoringAlgorithm, you can select options such as

the order in which vertices are processed (a subtype of AbstractOrder)
the type of decompression you want (:direct or :substitution)

algo = GreedyColoringAlgorithm()

GreedyColoringAlgorithm{:direct, NaturalOrder}(NaturalOrder(), false)

Coloring results

The coloring function takes a matrix, a problem and an algorithm, to return a result subtyping AbstractColoringResult.

S = sparse([
    0 0 1 1 0 1
    1 0 0 0 1 0
    0 1 0 0 1 0
    0 1 1 0 0 0
])

result = coloring(S, problem, algo)

SparseMatrixColorings.ColumnColoringResult{SparseArrays.SparseMatrixCSC{Int64, Int64}, Int64, SparseMatrixColorings.BipartiteGraph{Int64}, Vector{SubArray{Int64, 1, Vector{Int64}, Tuple{UnitRange{Int64}}, true}}}(sparse([2, 3, 4, 1, 4, 1, 2, 3, 1], [1, 2, 2, 3, 3, 4, 5, 5, 6], [1, 1, 1, 1, 1, 1, 1, 1, 1], 4, 6), SparseMatrixColorings.BipartiteGraph{Int64}([false true false false; false false true true; … ; false true true false; true false false false], [false false … false true; true false … true false; false true … true false; false true … false false]), [1, 1, 2, 1, 2, 3], SubArray{Int64, 1, Vector{Int64}, Tuple{UnitRange{Int64}}, true}[[1, 2, 4], [3, 5], [6]], [2, 3, 4, 5, 8, 1, 6, 7, 9])

The detailed type and fields of that result are not part of the public API. To access its contents, you can use the following getters:

sparsity_pattern for the matrix initially provided to coloring
ncolors for the total number of distinct colors
row_colors, column_colors for vectors of integer colors (depending on the partition)
row_groups, column_groups for vector of row or column indices grouped by color (depending on the partition)

Here, we have a column coloring, so we can try the following:

column_colors(result)

6-element Vector{Int64}:
 1
 1
 2
 1
 2
 3

column_groups(result)

3-element Vector{SubArray{Int64, 1, Vector{Int64}, Tuple{UnitRange{Int64}}, true}}:
 [1, 2, 4]
 [3, 5]
 [6]

ncolors(result)

Compression and decompression

The functions compress and decompress efficiently store and retrieve compressed representations of sparse matrices, using the coloring result as a starting point.

Compression sums all columns or rows with the same color:

M = sparse([
    0 0 4 6 0 9
    1 0 0 0 7 0
    0 2 0 0 8 0
    0 3 5 0 0 0
])

B = compress(M, result)

4×3 Matrix{Int64}:
 6  4  9
 1  7  0
 2  8  0
 3  5  0

Decompression recovers the original matrix from its compressed version:

C = decompress(B, result)

4×6 SparseArrays.SparseMatrixCSC{Int64, Int64} with 9 stored entries:
 ⋅  ⋅  4  6  ⋅  9
 1  ⋅  ⋅  ⋅  7  ⋅
 ⋅  2  ⋅  ⋅  8  ⋅
 ⋅  3  5  ⋅  ⋅  ⋅

The functions decompress! and decompress_single_color! are in-place variants of decompress.

D = [
    10 14 18
    11 15 0
    12 16 0
    13 17 0
]

decompress!(C, D, result)

4×6 SparseArrays.SparseMatrixCSC{Int64, Int64} with 9 stored entries:
  ⋅   ⋅  14  10   ⋅  18
 11   ⋅   ⋅   ⋅  15   ⋅
  ⋅  12   ⋅   ⋅  16   ⋅
  ⋅  13  17   ⋅   ⋅   ⋅

nonzeros(C) .= -1
decompress_single_color!(C, D[:, 2], 2, result)

4×6 SparseArrays.SparseMatrixCSC{Int64, Int64} with 9 stored entries:
  ⋅   ⋅  14  -1   ⋅  -1
 -1   ⋅   ⋅   ⋅  15   ⋅
  ⋅  -1   ⋅   ⋅  16   ⋅
  ⋅  -1  17   ⋅   ⋅   ⋅

Unidirectional variants

We now illustrate the variants of colorings available, on the following matrix:

S = sparse(Symmetric(sprand(StableRNG(0), Bool, 10, 10, 0.4)))

10×10 SparseArrays.SparseMatrixCSC{Bool, Int64} with 31 stored entries:
 1  1  ⋅  1  1  ⋅  ⋅  ⋅  ⋅  ⋅
 1  1  1  ⋅  ⋅  1  ⋅  ⋅  ⋅  ⋅
 ⋅  1  ⋅  ⋅  ⋅  1  ⋅  ⋅  ⋅  ⋅
 1  ⋅  ⋅  1  ⋅  1  ⋅  ⋅  ⋅  ⋅
 1  ⋅  ⋅  ⋅  1  1  ⋅  ⋅  1  1
 ⋅  1  1  1  1  ⋅  ⋅  ⋅  ⋅  ⋅
 ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  1  ⋅
 ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  1  ⋅
 ⋅  ⋅  ⋅  ⋅  1  ⋅  1  1  ⋅  1
 ⋅  ⋅  ⋅  ⋅  1  ⋅  ⋅  ⋅  1  1

We start with unidirectional colorings, where only rows or columns are colored and the matrix is not assumed to be symmetric.

Column coloring

problem = ColoringProblem(; structure=:nonsymmetric, partition=:column)
algo = GreedyColoringAlgorithm(; decompression=:direct)
result = coloring(S, problem, algo)

ncolors(result), column_colors(result)

(6, [1, 2, 3, 4, 5, 6, 1, 2, 2, 3])

Here is the colored matrix

and its columnwise compression

Row coloring

problem = ColoringProblem(; structure=:nonsymmetric, partition=:row)
algo = GreedyColoringAlgorithm(; decompression=:direct)
result = coloring(S, problem, algo)

ncolors(result), row_colors(result)

(6, [1, 2, 3, 4, 5, 6, 1, 2, 2, 3])

Here is the colored matrix

and its rowwise compression

Symmetric variants

We continue with unidirectional symmetric colorings, where coloring rows is equivalent to coloring columns. Symmetry is leveraged to possibly reduce the number of necessary colors.

Star coloring

Star coloring is the algorithm used for symmetric matrices with direct decompression.

problem = ColoringProblem(; structure=:symmetric, partition=:column)
algo = GreedyColoringAlgorithm(; decompression=:direct)
result = coloring(S, problem, algo)

ncolors(result), column_colors(result)

(5, [1, 2, 1, 3, 3, 4, 1, 1, 2, 5])

Here is the colored matrix

and its columnwise compression

Acyclic coloring

Acyclic coloring is the algorithm used for symmetric matrices with decompression by substitution.

problem = ColoringProblem(; structure=:symmetric, partition=:column)
algo = GreedyColoringAlgorithm(; decompression=:substitution)
result = coloring(S, problem, algo)

ncolors(result), column_colors(result)

(3, [1, 2, 1, 2, 2, 3, 1, 1, 3, 1])

Here is the colored matrix

and its columnwise compression

Bidirectional variants

We finish with bidirectional colorings, where both rows and columns are colored and the matrix is not assumed to be symmetric.

Bicoloring is most relevant for matrices with dense rows and columns, which is why we consider the following test case:

S_bi = copy(S)
S_bi[:, 1] .= true
S_bi[1, :] .= true
S_bi

10×10 SparseArrays.SparseMatrixCSC{Bool, Int64} with 43 stored entries:
 1  1  1  1  1  1  1  1  1  1
 1  1  1  ⋅  ⋅  1  ⋅  ⋅  ⋅  ⋅
 1  1  ⋅  ⋅  ⋅  1  ⋅  ⋅  ⋅  ⋅
 1  ⋅  ⋅  1  ⋅  1  ⋅  ⋅  ⋅  ⋅
 1  ⋅  ⋅  ⋅  1  1  ⋅  ⋅  1  1
 1  1  1  1  1  ⋅  ⋅  ⋅  ⋅  ⋅
 1  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  1  ⋅
 1  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  1  ⋅
 1  ⋅  ⋅  ⋅  1  ⋅  1  1  ⋅  1
 1  ⋅  ⋅  ⋅  1  ⋅  ⋅  ⋅  1  1

With our implementations, bidirectional coloring works better using a RandomOrder.

Star bicoloring

problem = ColoringProblem(; structure=:nonsymmetric, partition=:bidirectional)
algo = GreedyColoringAlgorithm(RandomOrder(StableRNG(0), 0); decompression=:direct)
result = coloring(S_bi, problem, algo)

ncolors(result), column_colors(result)

(9, [1, 2, 2, 2, 3, 2, 2, 2, 4, 2])

Here is the colored matrix

its columnwise compression

and rowwise compression

Both are necessary to reconstruct the original.

Acyclic bicoloring

problem = ColoringProblem(; structure=:nonsymmetric, partition=:bidirectional)
algo = GreedyColoringAlgorithm(RandomOrder(StableRNG(0), 0); decompression=:substitution)
result = coloring(S_bi, problem, algo)

ncolors(result), column_colors(result)

(8, [1, 2, 2, 3, 4, 2, 2, 2, 3, 5])

Here is the colored matrix

its columnwise compression

and rowwise compression

Both are necessary to reconstruct the original.