Content
This page contains a brief discussion of the background for, the functionalities available in,
and the organization of our serial coloring software package ColPack. For a detailed discussion
of the algorithms on which the package relies, consult the Papers page.
Sparse
derivative computation and coloring
Fourstep procedure
The computation of an mbyn
sparse derivative matrix A using automatic
differentiation (AD) can be made efficient by using the following
fourstep procedure.
 Determine the sparsity structure of A.
 Using a
specialized vertex coloring
on an appropriate graph representation of the matrix A, obtain an nbyp seed
matrix S that defines a partitioning of the columns of A into p groups with p as small as possible.
 Compute the compressed matrix B = AS using AD.
 Recover the numerical
values of the entries of A from B.
The set of criteria used to define the seed matrix S
in the second step, the partitioning problem on the matrix A,
depends on three mutually orthogonal factors:
 Whether the
derivative matrix being computed is a Jacobian (nonsymmetric) or a Hessian (symmetric),
 Whether the
numerical values of the entries of the original matrix A are obtained from the compressed representation B directly
(without any further arithmetic) or indirectly (for example, by solving for unknowns via
successive substitution), and
 Whether the
matrix partitioning is unidirectional
(involving only columns or only rows) or bidirectional (involving both columns and rows). The
fourstep procedure above is described assuming a columnwise
unidirectional partitioning. In a rowwise unidirectional
partitioning (which is a better approach for Jacobian matrices
with a few dense rows), the compressed matrix would correspond to
the seedmatrixJacobian product S^{T}A.
Similarly, in a bidirectional partitioning (which might be the
best approach for Jacobian matrices with both a few dense rows and
a few dense columns), the Jacobian entries are recovered from two
compressed matrices S_{1}^{T}A
and AS_{2}.
Coloring models
Table 1 below provides a summary of the most
accurate coloring models for the various computational scenarios. In
each case, the structure of a Jacobian matrix A is represented
by the bipartite graph G_{b}(A) = (V_{1},
V_{2}, E), where the vertex sets V_{1} and
V_{2} represent the rows and columns of A,
respectively, and each nonzero matrix entry A_{ij} is
represented by the edge (r_{i }, c_{j})
in E. Analogously, the structure of a Hessian matrix A
is represented by the adjacency
graph G(A) = (V, E), where the vertex set V
represents the columns (or, by symmetry, the rows) of A
and each offdiagonal nonzero matrix entry A_{ij}
(and its symmetric counterpart A_{ji})
is represented by the single edge (c_{i}, c_{j})
in E.

1d partition

2d partition


Jacobian

Partial
distance2 coloring

Star
bicoloring

Direct

Hessian

Star coloring

NA

Direct

Jacobian

NA

Acyclic
bicoloring

Substitution

Hessian

Acyclic
coloring

NA

Substitution

Table 1: Overview of
coloring models in derivative computation. NA
stands for not applicable.
In a graph G = (V, E), two distinct
vertices are distancek neighbors if a shortest
path connecting them consists of at most k edges. A distancek coloring of the graph is an assignment of positive
integers (called colors) to the vertices such that every two distancek
neighboring vertices get different colors. A star coloring is a distance1 coloring where, in addition,
every path on four vertices uses at least three colors. An acyclic coloring is a distance1
coloring in which every cycle uses at least three colors. The names
star and acyclic coloring are due to the structures of twocolored induced subgraphs: a
collection of stars in the case of star coloring and a collection of
trees in the case of acyclic coloring.
In a bipartite graph G_{b} = (V_{1},
V_{2}, E), a partial
distance2 coloring on the vertex set V_{i}, i = 1,2,
is an assignment of colors to the vertices in V_{i} such
that any two vertices connected by a path of length exactly two edges
receive different colors. Star
and acyclic bicoloring in a bipartite graph are defined in a manner
analogous to star and acyclic coloring in a general graph, but with the
additional stipulation that the set of colors assigned to row vertices
(V_{1}) is disjoint from the set of colors used
for column vertices (V_{2}).
ColPack : functionalities
ColPack is a package comprising of implementations of
algorithms for the specialized vertex coloring problems discussed in
the previous section as well as algorithms for a variety of related
supporting tasks in derivative computation.
Coloring capabilities
Table 2 below gives a quick summary of all the coloring
problems (on general and bipartite graphs) supported by ColPack.
General
Graph G = (V, E)

Bipartite Graph G_{b} = (V_{1}, V_{2}, E):
Onesided
Coloring

Bipartite Graph G_{b} = (V_{1}, V_{2}, E):
Bicoloring

·
Distance1 coloring
O(V∙d_{1}) = O(E)

_{·
}Partial
distance2 coloring on V_{2
}_{}
O(V_{2}· d(V_{2})
· Δ(V_{1})) = O (E·Δ(V_{1}))

·
Star
bicoloring^{†}
O((V_{1}+ V_{2})∙d_{2}))

·
Distance2
coloring
O(V∙d_{2})

_{·
}Partial
distance2 coloring on V_{1}_{}
O(V_{1}· d(V_{1})
· Δ(V_{2})) = O(E·Δ(V_{2}))

^{ }

·
Star coloring^{†}
O(V∙d_{2})^{ }



·
Acyclic
coloring
O(V∙d_{2}∙α)



·
Restricted
star coloring
O(V∙d_{2})



·
Triangular
coloring^{†}
O(V∙d_{2})^{ }



Table
2: List of coloring problems for which implementations of algorithms
are available in ColPack. Problems with the superscript ^{†}
have more than one algorithm implemented in ColPack; the complexity
listed in each case is that of the fastest algorithm.
All of the coloring problems listed in Table 2 are
NPhard. Their corresponding algorithms in ColPack are greedy heuristics in the sense
that the algorithms progressively extend a partial coloring by
processing one vertex at a time, in some order, in each step assigning
a vertex the smallest allowable color. Listed beneath each coloring
problem in Table 2 is the complexity of the corresponding algorithm in
ColPack. In the cases where ColPack has multiple algorithms for a
problem (these are designated by the superscript ^{†}), the
complexity expression corresponds to that of the fastest algorithm. In
the complexity expressions,
 d_{k} denotes the average degreek, the number of distinct paths of length at most k edges leaving a vertex. Thus d_{1}(v) corresponds to the usual degree
of the vertex v, the number of edges incident on v, and d_{2}(v)
corresponds to the sum of the degree1 values of the vertices
adjacent to v.
 α denotes the inverse of Ackermann’s
function.
 d(V_{i}) and Δ(V_{i})
denote the average and maximum, respectively, vertex degree1 in
the set V_{i}, i=1,2,
of the bipartite graph G_{b} = (V_{1},
V_{2} , E).
Ordering techniques
The order in which vertices are processed in a
greedy coloring algorithm determines the number of colors used by the
algorithm. ColPack has implementations of various effective ordering
techniques for each of the supported coloring problems. These are
summarized in Table 3 below.
General
Graph

Bipartite
Graph: Onesided Coloring

Bipartite
Graph: Bicoloring

·
Natural

·
Column Natural

·
Natural

·
Largest First

·
Column Largest
First

·
Largest First

·
Smallest Last

·
Column
Smallest Last

·
Smallest Last

·
Incidence
Degree

·
Column
Incidence Degree

·
Incidence
Degree

·
Dynamic
Largest First

·
Row Natural

·
Dynamic
Largest First

·
Distance2
Largest First

·
Row Largest
First

·
Selective
Largest First

·
Distance2 Smallest
Last

·
Row Smallest
Last

·
Selective
Smallest Last

·
Distance2
Incidence Degree

·
Row Incidence
Degree

·
Selective
Incidence Degree

·
Distance2
Dynamic Largest First



Recovery routines
Besides coloring and ordering capabilities, ColPack
also has routines for recovering the numerical values of the entries of
a derivative matrix from a compressed representation. In particular the
following reconstruction routines are currently available:
 Recovery
routines for direct (via star coloring ) and substitutionbased
(via acyclic coloring) Hessian computation
 Recovery
routines for unidirectional, direct Jacobian computation (via
columnwise or rowwise distance2 coloring)
 Recovery
routines for bidirectional, direct Jacobian computation via star
bicoloring
Graph construction routines
Finally, as a supporting functionality, ColPack has
routines for constructing bipartite graphs (for Jacobians) and
adjacency graphs (for Hessians) from files specifying matrix sparsity
structures in various formats, including Matrix Market, HarwellBoeing
and MeTis.
ColPack : organization
ColPack is written in an objectoriented fashion in
C++ heavily using the Standard Template Library (STL).
It is designed to be simple, modular, extensible and efficient.
Figure 1 below gives an overview
of the structure of the major classes of ColPack.
Figure 1: Overview of the
structure of the major classes in ColPack. A solid arrow indicates an
inheritancerelationship, and a broken arrow indicates a
usesrelationship.
ColPack functions that a user needs to call
directly are made available via the appropriate Interface classes.
Sample Codes
The following sample codes illustrate how ColPack
functions are called in the context of sparse derivative computation
via the Fourstep Procedure. In each sample code, the decompressed sparse derivative matrix is
returned in the Coordinate Format (zerobased indexing).
Recovery routines that return the decompressed matrix in
Direct Sparse Solver and ADOLC Formats are also available in ColPack.
Columnwise Jacobian Computation (via partial
distance2 coloring)
Rowwise Jacobian Computation (via partial distance2
coloring)
Direct Hessian Computation (via star coloring)
Indirect Hessian Computation (via acyclic coloring)
Bidirectional, direct Jacobian Computation (via star
bicoloring)
Download
Here is the source code of ColPack. It is being distributed under the GNU Lesser General Public
License.
ColPack
And here are a few test graphs for experiments.
Graph
Collection in MeTis format
Graph
Collection in Matrix Market format
Complete Doxygen documentation of ColPack
