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}

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

The adjacency graph of a symmetrix matric 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)

Fields

• S::SparsityPatternCSC{T}

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=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.

partial_distance2_coloring(bg::BipartiteGraph, ::Val{side}, order::AbstractOrder)

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

symmetric_coefficient(
    i::Integer, j::Integer,
    color::AbstractVector{<:Integer},
    star_set::StarSet
)

Return the indices (k, c) such that A[i, j] = B[k, c], where A is the uncompressed symmetric matrix and B is the column-compressed matrix.

This function corresponds to algorithm DirectRecover2 in the paper.

References

Efficient Computation of Sparse Hessians Using Coloring and Automatic Differentiation, Gebremedhin et al. (2009), Figure 3

star_coloring(g::AdjacencyGraph, order::AbstractOrder)

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.

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, order::AbstractOrder)

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.

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::Vector{Int})

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

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

StarSet

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

Fields

• star::Dict{Tuple{Int64, Int64}, Int64}: a mapping from edges (pair of vertices) to their star index

• hub::Vector{Int64}: 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)

• spokes::Vector{Vector{Int64}}: a mapping from star indices to the vector of their spokes

TreeSet

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

Fields

• forest::DataStructures.DisjointSets{Tuple{Int64, Int64}}: a forest of two-colored trees

struct ColumnColoringResult{M<:(AbstractMatrix), G<:SparseMatrixColorings.BipartiteGraph, V} <: 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::Vector{Int64}: one integer color for each column or row (depending on partition)

• group::Any: color groups for columns or rows (depending on partition)

• compressed_indices::Vector{Int64}: 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]]

See also

• AbstractColoringResult

struct RowColoringResult{M<:(AbstractMatrix), G<:SparseMatrixColorings.BipartiteGraph, V} <: 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::Vector{Int64}

• group::Any

• compressed_indices::Vector{Int64}

See also

• AbstractColoringResult

struct StarSetColoringResult{M<:(AbstractMatrix), G<:SparseMatrixColorings.AdjacencyGraph, V} <: 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::Vector{Int64}

• group::Any

• star_set::SparseMatrixColorings.StarSet

• compressed_indices::Vector{Int64}

See also

• AbstractColoringResult

struct TreeSetColoringResult{M<:(AbstractMatrix), G<:SparseMatrixColorings.AdjacencyGraph, V, 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{Int64}

• group::Any

• vertices_by_tree::Vector{Vector{Int64}}

• reverse_bfs_orders::Vector{Vector{Tuple{Int64, Int64}}}

• diagonal_indices::Vector{Int64}

• diagonal_nzind::Vector{Int64}

• lower_triangle_offsets::Vector{Int64}

• upper_triangle_offsets::Vector{Int64}

• buffer::Vector

See also

• AbstractColoringResult

struct LinearSystemColoringResult{M<:(AbstractMatrix), G<:SparseMatrixColorings.AdjacencyGraph, V, 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{Int64}

• group::Any

• strict_upper_nonzero_inds::Vector{Tuple{Int64, Int64}}

• strict_upper_nonzeros_A::Vector

• T_factorization::Any

See also

• AbstractColoringResult

struct BicoloringResult{M<:(AbstractMatrix), G<:SparseMatrixColorings.AdjacencyGraph, decompression, V, 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: adjacency graph that was used for coloring (constructed from the bipartite graph)

• column_color::Vector{Int64}: one integer color for each column

• row_color::Vector{Int64}: one integer color for each row

• column_group::Any: color groups for columns

• row_group::Any: color groups for rows

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

• col_color_ind::Dict{Int64, Int64}: column color to index

• row_color_ind::Dict{Int64, Int64}: row color to index

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

• large_colptr::Vector{Int64}: CSC storage of A_and_noAᵀ -colptr`

• large_rowval::Vector{Int64}: CSC storage of A_and_noAᵀ -rowval`

See also

• AbstractColoringResult

remap_colors(color::Vector{Int})

Renumber the colors in color using their index in the vector sort(unique(color)), so that they are forced to go from 1 to some cmax contiguously.

Return a tuple (remapped_colors, color_to_ind) such that remapped_colors is a vector containing the renumbered colors and color_to_ind is a dictionary giving the translation between old and new color numberings.

For all vertex indices i we have:

remapped_color[i] = color_to_ind[color[i]]

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 symmetrix 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)

valid_dynamic_order(g::AdjacencyGraph, π::AbstractVector{Int}, order::DynamicDegreeBasedOrder)
valid_dynamic_order(bg::AdjacencyGraph, ::Val{side}, π::AbstractVector{Int}, 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 the JuliaImages ecosystem.

• For :column or :row colorings, it returns a tuple (A_img, B_img).
• For :bidirectional colorings, it returns a tuple (A_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::Colorant: color used for zero matrix entries and pad. Defaults to RGBA(0,0,0,0), a transparent background.
• scale::Int: scale the size of matrix entries to scale × scale pixels. Defaults to 1.
• pad::Int: set padding between matrix entries, in pixels. Defaults to 0.

For a matrix of size (n, m), the resulting output will be of size (n * (scale + pad) + pad, m * (scale + 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.