|
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
Four-step procedure
The computation of an m-by-n
sparse derivative matrix A using automatic
differentiation (AD) can be made efficient by using the following
four-step procedure.
- Determine the sparsity structure of A.
- Using a
specialized vertex coloring
on an appropriate graph representation of the matrix A, obtain an n-by-p 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
four-step procedure above is described assuming a column-wise
unidirectional partitioning. In a row-wise unidirectional
partitioning (which is a better approach for Jacobian matrices
with a few dense rows), the compressed matrix would correspond to
the seed-matrix-Jacobian product STA.
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 S1TA
and AS2.
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 Gb(A) = (V1,
V2, E), where the vertex sets V1 and
V2 represent the rows and columns of A,
respectively, and each nonzero matrix entry Aij is
represented by the edge (ri , cj)
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 off-diagonal nonzero matrix entry Aij
(and its symmetric counterpart Aji)
is represented by the single edge (ci, cj)
in E.
|
|
1d partition
|
2d partition
|
|
|
Jacobian
|
Partial
distance-2 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 distance-k neighbors if a shortest
path connecting them consists of at most k edges. A distance-k coloring of the graph is an assignment of positive
integers (called colors) to the vertices such that every two distance-k
neighboring vertices get different colors. A star coloring is a distance-1 coloring where, in addition,
every path on four vertices uses at least three colors. An acyclic coloring is a distance-1
coloring in which every cycle uses at least three colors. The names
star and acyclic coloring are due to the structures of two-colored 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 Gb = (V1,
V2, E), a partial
distance-2 coloring on the vertex set Vi, i = 1,2,
is an assignment of colors to the vertices in Vi 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
(V1) is disjoint from the set of colors used
for column vertices (V2).
A distance-2 coloring of the adjacency graph of a
Hessian and a partial distance-2 coloring on the column vertices of the
bipartite graph of a Jacobian each correspond to a structurally orthogonal column partition in the
corresponding matrix. Structural orthogonality is a basic partitioning
criterion used in direct methods for sparse derivative computation via
compression. Thus distance-2 coloring can be viewed as an archetypal
model in derivative matrix computation.
For Hessian computation, coloring models that are
based on the adjacency graph representation but are less accurate than
the star and acyclic coloring models exist. These models are distance-2
coloring (for a direct method that disregards the available symmetry),
restricted star coloring (for a direct method that exploits symmetry
only partially), and triangular coloring (for a substitution method that exploits symmetry only
partially). A restricted star
coloring is a distance-1 coloring where, in addition, in every path
v, w, x on three vertices, the terminal vertices v
and x are allowed to have the same color, but only if the
color of the middle vertex w is lower in value. A color
assignment is a triangular
coloring if there exists a vertex ordering such that the assignment is a distance-1 coloring
and in every path v, w, x on three vertices,
the terminal vertices v and x receive
different colors whenever the middle vertex w comes after
both of the vertices v and x in the
ordering.
The coloring variants introduced thus far can be
ranked in an increasing order of restriction in the following manners.
In each ordered list, each coloring variant necessarily satisfies all
of the conditions in the variant immediately preceding it (and by
extension all others before that).
- Distance-1
coloring, acyclic coloring, star coloring, restricted star
coloring, distance-2 coloring
- Distance-1
coloring, acyclic coloring, triangular coloring, restricted star
coloring, distance-2 coloring
- Acyclic
bicoloring, star bicoloring, partial distance-2 coloring
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 Gb = (V1, V2, E):
One-sided
Coloring
|
Bipartite Graph Gb = (V1, V2, E):
Bicoloring
|
|
·
Distance-1 coloring
O(|V|∙d1) = O(|E|)
|
·
Partial
distance-2 coloring on V2
O(|V2|· d(V2)
· Δ(V1)) = O (|E|·Δ(V1))
|
·
Star
bicoloring†
O((|V1|+ |V2|)∙d2))
|
|
·
Distance-2
coloring
O(|V|∙d2)
|
·
Partial
distance-2 coloring on V1
O(|V1|· d(V1)
· Δ(V2)) = O(|E|·Δ(V2))
|
|
|
·
Star coloring†
O(|V|∙d2)
|
|
|
|
·
Acyclic
coloring
O(|V|∙d2∙α)
|
|
|
|
·
Restricted
star coloring
O(|V|∙d2)
|
|
|
|
·
Triangular
coloring†
O(|V|∙d2)
|
|
|
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
NP-hard. 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,
- dk denotes the average degree-k, the number of distinct paths of length at most k edges leaving a vertex. Thus d1(v) corresponds to the usual degree
of the vertex v, the number of edges incident on v, and d2(v)
corresponds to the sum of the degree-1 values of the vertices
adjacent to v.
- α denotes the inverse of Ackermann’s
function.
- d(Vi) and Δ(Vi)
denote the average and maximum, respectively, vertex degree-1 in
the set Vi, i=1,2,
of the bipartite graph Gb = (V1,
V2 , E).
As can be gathered from the respective definitions,
the conditions in a distance-1 coloring involve the distance-1
neighborhood of each vertex, and the conditions in a distance-2,
restricted star, and triangular coloring involve the distance-2
neighborhood of each vertex. The greedy algorithms in ColPack for each
of these problems impose the coloring conditions by visiting the
appropriate neighborhood of each vertex exactly once. This fact is
alluded to by the factor dk embedded in
the complexity expressions for these problems as listed in Table 2.
On the other hand, the coloring conditions in a
star coloring involve the distance-3 neighborhood of each vertex, and
the conditions in an acyclic coloring involve an arbitrarily large
neighborhood. An approach that attempts to impose these condition in a
straightforward manner would result in an O(|V|∙d3)-time
algorithm for star coloring and possibly much slower algorithm for
acyclic coloring. (In fact, an O(|V|∙d3)-time
naïve star coloring algorithm, that chooses a color for each vertex by
traversing every path of length three edges leaving the vertex, is
available in ColPack). Instead, the algorithms for star and acyclic
coloring in ColPack take advantage of the special structures of two-colored induced subgraphs in
such colorings. By so doing and with appropriate data structures and
proper bookkeeping, each algorithm achieves its goal by visiting the
distance-2 neighborhood of each vertex at most twice, a fact reflected
in the complexity expressions given in Table 2. In the acyclic coloring
case, the collection of two-colored induced subgraphs (the collection
of trees) is maintained using the disjoint-set
data structure. The factor α in the complexity
expression is associated with efficient implementations of the
disjoint-set operations Find
and Union.
For star bicoloring (of bipartite graphs), a number
of algorithms are available in ColPack. The algorithmic variations here
stem from two orthogonal sources: a) whether two-colored induced
subgraphs are maintained or paths are traversed and b) whether the
vertex cover implied in a bicoloring is computed explicitly in a
pre-coloring step or it is computed implicitly as the coloring proceeds.
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: One-sided 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
|
|
·
Distance-2
Largest First
|
·
Row Largest
First
|
·
Selective
Largest First
|
|
·
Distance-2 Smallest
Last
|
·
Row Smallest
Last
|
·
Selective
Smallest Last
|
|
·
Distance-2
Incidence Degree
|
·
Row Incidence
Degree
|
·
Selective
Incidence Degree
|
|
·
Distance-2
Dynamic Largest First
|
|
|
Table 3: List of
ordering techniques implemented in ColPack.
The ordering techniques in the upper half of the
first column of Table 3 are primarily intended for distance-1 coloring,
and those in the lower half are intended for colorings that involve
visits to the distance-2 neighborhood of vertices. Similarly, ordering
techniques in the upper half of the second column are meant for
column-wise partial distance-2 coloring in a bipartite graph, and those
in the lower half are meant for row-wise partial distance-2 coloring.
The ordering techniques in the last column are for star and acyclic
bicoloring.
The ordering techniques listed in Table 3 rely on
the use of some notion of “degree”. In Table 4 below we describe the
properties of the “core”
ordering variants, the variants applicable to the case of distance-1 coloring
of a general graph G = (V, E) on n
vertices. For the cases where a visit to at least the distance-2
neighborhood of a vertex in a graph is required or the coloring is
performed on a bipartite graph, the notion of degree is suitably
adapted; the basic ideas remain essentially the same otherwise.
|
Ordering
variant
|
Property
|
|
Natural
|
Vertices
appear in the original ordering given in the input graph.
|
|
Largest
First
|
Vertices are
sorted in a non-increasing
order of their degrees in the input graph G.
|
|
Smallest
Last
|
Let the last
vertex vn in the ordering be a vertex v of the smallest
degree in Gn = G. Remove v and its incident edges from Gn
to obtain the smaller graph Gn-1. Pick a
new vertex v of the smallest degree
in the graph Gn-1. Let v be vertex vn-1 in the
ordering. Remove v and its incident edges
from Gn-1 to obtain the smaller graph Gn-2..Continue in this manner until the
ordering v1 , v2
, ..., vn is
obtained.
|
|
Incidence
Degree
|
The ith vertex in the ordering is a vertex having the
maximum incidence degree,
the number of neighbors in the sequence v1 , v2 , ..., vi-1
|
|
Dynamic
Largest First
|
Let the first
vertex v1 in the ordering be a vertex v of the largest
degree in Gn = G. Remove v and its incident edges from Gn
to obtain the smaller graph Gn-1. Pick a
new vertex v of the largest degree in
the graph Gn-1. Let v be vertex v2 in the ordering. Remove v and its incident edges from Gn-1 to
obtain the smaller graph Gn-2..Continue
in this manner until the ordering v1 , v2 , ..., vn is
obtained.
|
Table 4: Properties of ordering
techniques.
In ColPack, each ordering technique listed in Table
3 is implemented in such a way that its time complexity is
upper-bounded by the complexity of the relevant coloring algorithm.
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 substitution-based
(via acyclic coloring) Hessian computation
- Recovery
routines for unidirectional, direct Jacobian computation (via
column-wise or row-wise distance-2 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, Harwell-Boeing
and MeTis.
ColPack : organization
ColPack is written in an object-oriented fashion in
C++ heavily using the Standard Template Library (STL).
It is designed to be simple, modular, extendable and efficient.
On the one hand, different functionalities have been encapsulated into
different classes and on the other hand, these classes have been
related via inheritance so as to reduce data access overheads generally
associated with object-oriented codes. 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
inheritance-relationship, and a broken arrow indicates a
uses-relationship.
The entire ColPack package is under the ColPack namespace. Two core
classes, GraphCore and BipartiteGraphCore, are used to
store the general graph and bipartite graph, respectively, data
structures in Compact Edge
Storage (CES) formats. The
CES format consists essentially of two one-dimensional integer arrays
(vectors), one corresponding to vertices and the other to edges. The
classes GraphCore and BipartiteGraphCore are abstract
(pure virtual) with no useful methods to manipulate the graph and
bipartite graph data. The
classes GraphInputOutput and BipartiteGraphInputOutput, which
contain methods for constructing graphs by reading files from disc,
inherit the classes GraphCore
and BipartiteGraphCore,
respectively. The class GraphInputOutput
starts up an inheritance chain collectively containing implementations
of coloring and ordering algorithms for general graphs. For a similar purpose on bipartite
graphs, the class BipartiteGraphInputOutput
starts up two separate inheritance chains, one concerning partial
distance-2 coloring and the other bicoloring. The classes HessianRecovery, JacobianRecovery1D
and JacobianRecovery2D house
the appropriate routines for reconstructing a derivative matrix from its
compressed representation.
ColPack functions that a user needs to call
directly are made available via the appropriate Interface classes.
The linear inheritance adopted in the design of
ColPack allows for easy extension in two ways: Either a new inheritance
chain can be started from any class or a new inherited and extended
class at any level can be put into an existing chain.
Sample Codes
The following sample codes illustrate how ColPack
functions are called in the context of sparse derivative computation
via the Four-step Procedure. In each sample code, the de-compressed sparse derivative matrix is
returned in the Coordinate Format (zero-based indexing).
Recovery routines that return the de-compressed matrix in
Direct Sparse Solver and ADOL-C Formats are also available in ColPack.
Column-wise Jacobian Computation (via partial
distance-2 coloring)
Row-wise Jacobian Computation (via partial distance-2
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.tar.gz
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
|
|
Software |