Internals

SparsityPatternCSC{Ti<:Integer}

Store a sparse matrix (in CSC) without its values, keeping only the pattern of nonzeros.

Fields

Copied from SparseMatrixCSC:

• m::Int: number of rows
• n::Int: number of columns
• colptr::Vector{Ti}: column j is in colptr[j]:(colptr[j+1]-1)
• rowval::Vector{Ti}: row indices of stored values

AdjacencyGraph{T,augmented_graph}

Undirected graph without self-loops representing the nonzeros of a symmetric matrix (typically a Hessian matrix).

The adjacency graph of a symmetric matrix A ∈ ℝ^{n × n} is G(A) = (V, E) where

• V = 1:n is the set of rows or columns i/j
• (i, j) ∈ E whenever A[i, j] ≠ 0 and i ≠ j

Constructors

AdjacencyGraph(A::SparseMatrixCSC; augmented_graph::Bool=false)

Fields

• S::SparsityPatternCSC{T}: Underlying sparsity pattern, which represents an augmented graph whenever augmented_graph is true. Here, "augmented graph" means the sparsity pattern of the augmented matrix H = [0 Jᵀ; J 0].
• edge_to_index::Vector{T}: A vector mapping each nonzero of S to a unique edge index (ignoring diagonal and accounting for symmetry, so that (i, j) and (j, i) get the same index)

References

What Color Is Your Jacobian? SparsityPatternCSC Coloring for Computing Derivatives, Gebremedhin et al. (2005)

BipartiteGraph{T}

Undirected bipartite graph representing the nonzeros of a non-symmetric matrix (typically a Jacobian matrix).

The bipartite graph of a matrix A ∈ ℝ^{m × n} is Gb(A) = (V₁, V₂, E) where

• V₁ = 1:m is the set of rows i
• V₂ = 1:n is the set of columns j
• (i, j) ∈ E whenever A[i, j] ≠ 0

A BipartiteGraph has two sets of vertices, one for the rows of A (which we call side 1) and one for the columns (which we call side 2).

Constructors

BipartiteGraph(A::SparseMatrixCSC; symmetric_pattern::Bool=false)

When symmetric_pattern is true, this construction is more efficient.

Fields

• S1::SparsityPatternCSC{T}: maps vertices on side 1 to their neighbors
• S2::SparsityPatternCSC{T}: maps vertices on side 2 to their neighbors

References

What Color Is Your Jacobian? SparsityPatternCSC Coloring for Computing Derivatives, Gebremedhin et al. (2005)

vertices(bg::BipartiteGraph, Val(side))

Return the list of vertices of bg from the specified side as a range 1:n.

neighbors(bg::BipartiteGraph, Val(side), v::Integer)

Return the neighbors of v (a vertex from the specified side, 1 or 2), in the graph bg.

transpose(S::SparsityPatternCSC)

Return a SparsityPatternCSC corresponding to the transpose of S.

bidirectional_pattern(A::AbstractMatrix; symmetric_pattern::Bool)

Return a SparsityPatternCSC corresponding to the matrix [0 Aᵀ; A 0], with a minimum of allocations.

partial_distance2_coloring(
    bg::BipartiteGraph, ::Val{side}, vertices_in_order::AbstractVector;
    forced_colors::Union{AbstractVector{<:Integer},Nothing}=nothing
)

Compute a distance-2 coloring of the given side (1 or 2) in the bipartite graph bg and return a vector of integer colors.

A distance-2 coloring is such that two vertices have different colors if they are at distance at most 2.

The vertices are colored in a greedy fashion, following the order supplied.

The optional forced_colors keyword argument is used to enforce predefined vertex colors (e.g. coming from another optimization algorithm) but still run the distance-2 coloring procedure to verify correctness.

See also

• BipartiteGraph
• AbstractOrder

References

What Color Is Your Jacobian? Graph Coloring for Computing Derivatives, Gebremedhin et al. (2005), Algorithm 3.2

star_coloring(
    g::AdjacencyGraph, vertices_in_order::AbstractVector, postprocessing::Bool;
    forced_colors::Union{AbstractVector,Nothing}=nothing
)

Compute a star coloring of all vertices in the adjacency graph g and return a tuple (color, star_set), where

• color is the vector of integer colors
• star_set is a StarSet encoding the set of 2-colored stars

A star coloring is a distance-1 coloring such that every path on 4 vertices uses at least 3 colors.

The vertices are colored in a greedy fashion, following the order supplied.

If postprocessing=true, some colors might be replaced with 0 (the "neutral" color) as long as they are not needed during decompression.

The optional forced_colors keyword argument is used to enforce predefined vertex colors (e.g. coming from another optimization algorithm) but still run the star coloring procedure to verify correctness and build auxiliary data structures, useful during decompression.

See also

• AdjacencyGraph
• AbstractOrder

References

New Acyclic and Star Coloring Algorithms with Application to Computing Hessians, Gebremedhin et al. (2007), Algorithm 4.1

acyclic_coloring(g::AdjacencyGraph, vertices_in_order::AbstractVector, postprocessing::Bool)

Compute an acyclic coloring of all vertices in the adjacency graph g and return a tuple (color, tree_set), where

• color is the vector of integer colors
• tree_set is a TreeSet encoding the set of 2-colored trees

An acyclic coloring is a distance-1 coloring with the further restriction that every cycle uses at least 3 colors.

The vertices are colored in a greedy fashion, following the order supplied.

If postprocessing=true, some colors might be replaced with 0 (the "neutral" color) as long as they are not needed during decompression.

See also

• AdjacencyGraph
• AbstractOrder

References

New Acyclic and Star Coloring Algorithms with Application to Computing Hessians, Gebremedhin et al. (2007), Algorithm 3.1

group_by_color(color::AbstractVector{<:Integer})

Create a color-indexed vector group such that i ∈ group[c] iff color[i] == c for all c > 0.

Assumes the colors are contiguously numbered from 0 to some cmax.

mutable struct Forest{T<:Integer}

Structure that provides fast union-find operations for constructing a forest during acyclic coloring and bicoloring.

Fields

• nt::Integer: current number of distinct trees in the forest

• parents::Vector{T} where T<:Integer: vector storing the index of a parent in the tree for each edge, used in union-find operations

• ranks::Vector{T} where T<:Integer: vector approximating the depth of each tree to optimize path compression

StarSet

Encode a set of 2-colored stars resulting from the star_coloring algorithm.

Fields

• star::Vector: a mapping from edges (pair of vertices) to their star index

• hub::Vector: a mapping from star indices to their hub (undefined hubs for single-edge stars are the negative value of one of the vertices, picked arbitrarily)

TreeSet

Encode a set of 2-colored trees resulting from the acyclic_coloring algorithm.

Fields

• reverse_bfs_orders::Array{Tuple{T, T}, 1} where T: For a tree index 1 <= k <= nt, the list list = reverse_bfs_order[tree_edge_indices[k]:(tree_edge_indices[k+1]-1)] is a list of edges list[i] = (leaf, inner) of the kth tree such that leaf is a leaf of the tree containing the edges list[i:end]. From an other point of view, reverse(list) contains the edges in the order of a breadth first (BFS) traversal order of the kth tree starting from a depth-minimizing root.

• is_star::Vector{Bool}: For a tree index 1 <= k <= nt, is_star[k] indicates whether the kth three is a star.

• tree_edge_indices::Vector: tree_edge_indices[1] is one and tree_edge_indices[k+1] - tree_edge_indices[k] is the number of edges in the kth tree. One can think of it as a kind of fused vector of offsets (similar to the colptr field of SparseMatrixCSC) of all trees together.

• nt::Any: numbers of 2-colored trees for which trees sharing the same 2 colors have disjoint edges

struct ColumnColoringResult{M<:(AbstractMatrix), T<:Integer, G<:SparseMatrixColorings.BipartiteGraph{T<:Integer}, CT<:AbstractArray{T<:Integer, 1}, GT<:(AbstractArray{<:AbstractArray{T<:Integer, 1}, 1}), VT<:AbstractArray{T<:Integer, 1}, A} <: AbstractColoringResult{:nonsymmetric, :column, :direct}

Storage for the result of a column coloring with direct decompression.

Fields

• A::AbstractMatrix: matrix that was colored

• bg::SparseMatrixColorings.BipartiteGraph: bipartite graph that was used for coloring

• color::AbstractVector{T} where T<:Integer: one integer color for each column or row (depending on partition)

• group::AbstractVector{<:AbstractVector{T}} where T<:Integer: color groups for columns or rows (depending on partition)

• compressed_indices::AbstractVector{T} where T<:Integer: flattened indices mapping the compressed matrix B to the uncompressed matrix A when A isa SparseMatrixCSC. They satisfy nonzeros(A)[k] = vec(B)[compressed_indices[k]]

• additional_info::Any: optional data used for decompressing into specific matrix types

See also

• AbstractColoringResult

struct RowColoringResult{M<:(AbstractMatrix), T<:Integer, G<:SparseMatrixColorings.BipartiteGraph{T<:Integer}, CT<:AbstractArray{T<:Integer, 1}, GT<:(AbstractArray{<:AbstractArray{T<:Integer, 1}, 1}), VT<:AbstractArray{T<:Integer, 1}, A} <: AbstractColoringResult{:nonsymmetric, :row, :direct}

Storage for the result of a row coloring with direct decompression.

Fields

See the docstring of ColumnColoringResult.

• A::AbstractMatrix

• bg::SparseMatrixColorings.BipartiteGraph

• color::AbstractVector{T} where T<:Integer

• group::AbstractVector{<:AbstractVector{T}} where T<:Integer

• compressed_indices::AbstractVector{T} where T<:Integer

• additional_info::Any

See also

• AbstractColoringResult

struct StarSetColoringResult{M<:(AbstractMatrix), T<:Integer, G<:(SparseMatrixColorings.AdjacencyGraph{T<:Integer}), CT<:AbstractArray{T<:Integer, 1}, GT<:(AbstractArray{<:AbstractArray{T<:Integer, 1}, 1}), VT<:AbstractArray{T<:Integer, 1}, A} <: AbstractColoringResult{:symmetric, :column, :direct}

Storage for the result of a symmetric coloring with direct decompression.

Fields

See the docstring of ColumnColoringResult.

• A::AbstractMatrix

• ag::SparseMatrixColorings.AdjacencyGraph

• color::AbstractVector{T} where T<:Integer

• group::AbstractVector{<:AbstractVector{T}} where T<:Integer

• compressed_indices::AbstractVector{T} where T<:Integer

• additional_info::Any

See also

• AbstractColoringResult

struct TreeSetColoringResult{M<:(AbstractMatrix), T<:Integer, G<:(SparseMatrixColorings.AdjacencyGraph{T<:Integer}), GT<:(AbstractArray{<:AbstractArray{T<:Integer, 1}, 1}), R} <: AbstractColoringResult{:symmetric, :column, :substitution}

Storage for the result of a symmetric coloring with decompression by substitution.

Fields

See the docstring of ColumnColoringResult.

• A::AbstractMatrix

• ag::SparseMatrixColorings.AdjacencyGraph

• color::Vector{T} where T<:Integer

• group::AbstractVector{<:AbstractVector{T}} where T<:Integer

• reverse_bfs_orders::Array{Tuple{T, T}, 1} where T<:Integer

• tree_edge_indices::Vector{T} where T<:Integer

• nt::Integer

• diagonal_indices::Vector{T} where T<:Integer

• diagonal_nzind::Vector{T} where T<:Integer

• lower_triangle_offsets::Vector{T} where T<:Integer

• upper_triangle_offsets::Vector{T} where T<:Integer

• buffer::Vector

See also

• AbstractColoringResult

struct LinearSystemColoringResult{M<:(AbstractMatrix), T<:Integer, G<:(SparseMatrixColorings.AdjacencyGraph{T<:Integer}), GT<:(AbstractArray{<:AbstractArray{T<:Integer, 1}, 1}), R, F} <: AbstractColoringResult{:symmetric, :column, :substitution}

Storage for the result of a symmetric coloring with any decompression.

Fields

See the docstring of ColumnColoringResult.

• A::AbstractMatrix

• ag::SparseMatrixColorings.AdjacencyGraph

• color::Vector{T} where T<:Integer

• group::AbstractVector{<:AbstractVector{T}} where T<:Integer

• strict_upper_nonzero_inds::Array{Tuple{T, T}, 1} where T<:Integer

• strict_upper_nonzeros_A::Vector

• M_factorization::Any

See also

• AbstractColoringResult

struct BicoloringResult{M<:(AbstractMatrix), T<:Integer, G<:(SparseMatrixColorings.AdjacencyGraph{T<:Integer}), decompression, GT<:(AbstractArray{<:AbstractArray{T<:Integer, 1}, 1}), SR<:AbstractColoringResult{:symmetric, :column, decompression}, R} <: AbstractColoringResult{:nonsymmetric, :bidirectional, decompression}

Storage for the result of a bidirectional coloring with direct or substitution decompression, based on the symmetric coloring of a 2x2 block matrix.

Fields

• A::AbstractMatrix: matrix that was colored

• abg::SparseMatrixColorings.AdjacencyGraph: augmented adjacency graph that was used for bicoloring

• column_color::Vector{T} where T<:Integer: one integer color for each column

• row_color::Vector{T} where T<:Integer: one integer color for each row

• column_group::AbstractVector{<:AbstractVector{T}} where T<:Integer: color groups for columns

• row_group::AbstractVector{<:AbstractVector{T}} where T<:Integer: color groups for rows

• symmetric_result::AbstractColoringResult{:symmetric, :column}: result for the coloring of the symmetric 2 x 2 block matrix

• symmetric_to_column::Vector{T} where T<:Integer: maps symmetric colors to column colors

• symmetric_to_row::Vector{T} where T<:Integer: maps symmetric colors to row colors

• Br_and_Bc::Matrix: combination of Br and Bc (almost a concatenation up to color remapping)

• large_colptr::Vector{T} where T<:Integer: CSC storage of A_and_noAᵀ -colptr`

• large_rowval::Vector{T} where T<:Integer: CSC storage of A_and_noAᵀ -rowval`

See also

• AbstractColoringResult

remap_colors(color::Vector{<:Integer}, num_sym_colors::Integer, m::Integer, n::Integer)

Return a tuple (row_color, column_color, symmetric_to_row, symmetric_to_column) such that row_color and column_color are vectors containing the renumbered colors for rows and columns. symmetric_to_row and symmetric_to_column are vectors that map symmetric colors to row and column colors.

For all vertex indices i between 1 and m we have:

row_color[i] = symmetric_to_row[color[n+i]]

For all vertex indices j between 1 and n we have:

column_color[j] = symmetric_to_column[color[j]]

directly_recoverable_columns(
    A::AbstractMatrix, color::AbstractVector{<:Integer}
    verbose=false
)

Return true if coloring the columns of the symmetric matrix A with the vector color results in a column-compressed representation that preserves every unique value, thus making direct recovery possible.

References

What Color Is Your Jacobian? Graph Coloring for Computing Derivatives, Gebremedhin et al. (2005)

symmetrically_orthogonal_columns(
    A::AbstractMatrix, color::AbstractVector{<:Integer};
    verbose=false
)

Return true if coloring the columns of the symmetric matrix A with the vector color results in a partition that is symmetrically orthogonal, and false otherwise.

A partition of the columns of a symmetric matrix A is symmetrically orthogonal if, for every nonzero element A[i, j], either of the following statements holds:

1. the group containing the column A[:, j] has no other column with a nonzero in row i
2. the group containing the column A[:, i] has no other column with a nonzero in row j

It is equivalent to a star coloring.

References

On the Estimation of Sparse Hessian Matrices, Powell and Toint (1979) Estimation of sparse hessian matrices and graph coloring problems, Coleman and Moré (1984) What Color Is Your Jacobian? Graph Coloring for Computing Derivatives, Gebremedhin et al. (2005)

structurally_orthogonal_columns(
    A::AbstractMatrix, color::AbstractVector{<:Integer};
    verbose=false
)

Return true if coloring the columns of the matrix A with the vector color results in a partition that is structurally orthogonal, and false otherwise.

A partition of the columns of a matrix A is structurally orthogonal if, for every nonzero element A[i, j], the group containing column A[:, j] has no other column with a nonzero in row i.

References

What Color Is Your Jacobian? Graph Coloring for Computing Derivatives, Gebremedhin et al. (2005)

structurally_biorthogonal(
    A::AbstractMatrix, row_color::AbstractVector{<:Integer}, column_color::AbstractVector{<:Integer};
    verbose=false
)

Return true if bicoloring of the matrix A with the vectors row_color and column_color results in a bipartition that is structurally biorthogonal, and false otherwise.

A bipartition of the rows and columns of a matrix A is structurally biorthogonal if, for every nonzero element A[i, j], either of the following statements holds:

1. the group containing the column A[:, j] has no other column with a nonzero in row i
2. the group containing the row A[i, :] has no other row with a nonzero in column j

It is equivalent to a star bicoloring.

substitutable_columns(
    A::AbstractMatrix, rank_nonzeros::AbstractMatrix, color::AbstractVector{<:Integer};
    verbose=false
)

Return true if coloring the columns of the symmetric matrix A with the vector color results in a partition that is substitutable, and false otherwise. For all nonzeros A[i, j], rank_nonzeros[i, j] provides its rank of recovery.

A partition of the columns of a symmetric matrix A is substitutable if, for every nonzero element A[i, j], either of the following statements holds:

1. the group containing the column A[:, j] has all nonzeros in row i ordered before A[i, j]
2. the group containing the column A[:, i] has all nonzeros in row j ordered before A[i, j]

It is equivalent to an acyclic coloring.

References

On the Estimation of Sparse Hessian Matrices, Powell and Toint (1979) The Cyclic Coloring Problem and Estimation of Sparse Hessian Matrices, Coleman and Cai (1986) What Color Is Your Jacobian? Graph Coloring for Computing Derivatives, Gebremedhin et al. (2005)

substitutable_bidirectional(
    A::AbstractMatrix, rank_nonzeros::AbstractMatrix, row_color::AbstractVector{<:Integer}, column_color::AbstractVector{<:Integer};
    verbose=false
)

Return true if bicoloring of the matrix A with the vectors row_color and column_color results in a bipartition that is substitutable, and false otherwise. For all nonzeros A[i, j], rank_nonzeros[i, j] provides its rank of recovery.

A bipartition of the rows and columns of a matrix A is substitutable if, for every nonzero element A[i, j], either of the following statements holds:

1. the group containing the column A[:, j] has all nonzeros in row i ordered before A[i, j]
2. the group containing the row A[i, :] has all nonzeros in column j ordered before A[i, j]

It is equivalent to an acyclic bicoloring.

rank_nonzeros_from_trees(result::TreeSetColoringResult)
rank_nonzeros_from_trees(result::BicoloringResult)

Construct a sparse matrix rank_nonzeros that assigns a unique recovery rank to each nonzero coefficient associated with an acyclic coloring or bicoloring.

For every nonzero entry result.A[i, j], rank_nonzeros[i, j] stores a strictly positive integer representing the order in which this coefficient is recovered during the decompression. A larger value means the coefficient is recovered later.

This ranking is used to test substitutability (acyclicity) of colorings: for a given nonzero result.A[i, j], the ranks allow one to check whether all competing nonzeros in the same row or column (within a color group) are recovered before it.

valid_dynamic_order(g::AdjacencyGraph, π::AbstractVector{<:Integer}, order::DynamicDegreeBasedOrder)
valid_dynamic_order(bg::AdjacencyGraph, ::Val{side}, π::AbstractVector{<:Integer}, order::DynamicDegreeBasedOrder)

Check that a permutation π corresponds to a valid application of a DynamicDegreeBasedOrder.

This is done by checking, for each ordered vertex, that its back- or forward-degree was the smallest or largest among the remaining vertices (the specifics depend on the order parameters).

respectful_similar(A::AbstractMatrix)
respectful_similar(A::AbstractMatrix, ::Type{T})

Like Base.similar but returns a transpose or adjoint when A is a transpose or adjoint.

matrix_versions(A::AbstractMatrix)

Return various versions of the same matrix:

• dense and sparse
• transpose and adjoint

Used for internal testing.

compatible_pattern(A::AbstractMatrix, bg::BipartiteGraph)
compatible_pattern(A::AbstractMatrix, ag::AdjacencyGraph, uplo::Symbol)

Perform a coarse compatibility check between the sparsity pattern of A and the reference sparsity pattern encoded in a graph structure.

This function only checks necessary conditions for the two sparsity patterns to match. In particular, it may return true even if the patterns are not identical.

When A is a SparseMatrixCSC, additional checks on the sparsity structure are performed.

Return value

• true : the sparsity patterns are potentially compatible
• false : the sparsity patterns are definitely incompatible

show_colors(result; kwargs...)

Create a visualization for an AbstractColoringResult, with the help of the JuliaImages ecosystem.

• For :column or :row colorings, it returns a couple (A_img, B_img).
• For :bidirectional colorings, it returns a 4-tuple (Ar_img, Ac_img, Br_img, Bc_img).

Keyword arguments

• colorscheme: colors used for non-zero matrix entries. This can be a vector of Colorants or a subsampled scheme from ColorSchemes.jl.
• background_color::Colorant: color used for zero matrix entries and pad. Defaults to RGBA(0,0,0,0), a transparent background.
• border_color::Colorant: color used around matrix entries. Defaults to RGB(0, 0, 0), a black border.
• scale::Int: scale the size of matrix entries to scale × scale pixels. Defaults to 1.
• border::Int: set border width around matrix entries, in pixles. Defaults to 0.
• pad::Int: set padding between matrix entries, in pixels. Defaults to 0.

For a matrix of size (m, n), the resulting output will be of size (m * (scale + 2border + pad) + pad, n * (scale + 2border + pad) + pad).

struct Example{TA<:(AbstractMatrix), TB<:(AbstractMatrix)}

Example coloring problem from one of our reference articles.

Used for internal testing.

Fields

• A::AbstractMatrix: decompressed matrix

• B::AbstractMatrix: column-compressed matrix

• color::Vector{Int64}: vector of colors

what_fig_41()

Construct an Example from Figure 4.1 of "What color is your Jacobian?", where the nonzero entries are filled with unique values.

what_fig_61()

Construct an Example from Figure 6.1 of "What color is your Jacobian?", where the nonzero entries are filled with unique values.

efficient_fig_1()

Construct an Example from Figure 1 of "Efficient computation of sparse hessians using coloring and AD", where the nonzero entries are filled with unique values.

efficient_fig_4()

Construct an Example from Figure 4 of "Efficient computation of sparse hessians using coloring and AD", where the nonzero entries are filled with unique values.