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,has_diagonal}

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; has_diagonal::Bool=true)

Fields

• S::SparsityPatternCSC{T}: Underlying sparsity pattern, whose diagonal is empty whenever has_diagonal is false
• 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)

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.

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)

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.

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

• is_star::Vector{Bool}

• tree_edge_indices::Vector

• nt::Any

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

References

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

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.

same_pattern(A, B)

Perform a partial equality check on the sparsity patterns of A and B:

• if the return is true, they might have the same sparsity pattern but we're not sure
• if the return is false, they definitely don't have the same sparsity pattern

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.