ColPack

Download

And here is a short document describing the major interface functions.

Short documentation.

• Sparse derivative computation and coloring
• Four-step procedure
• Coloring models
• ColPack : functionalities
• Coloring capabilities
• Ordering techniques
• Recovery routines
• Graph construction routines
• ColPack : organization
• Doxygen documentation of ColPack

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.

1. Determine the sparsity structure of A.
2. 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.
3. Compute the compressed matrix B = AS using AD.
4. 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 S^TA. 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₁^TA and AS₂.

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₁, V₂, E), where the vertex sets V₁ and V₂ 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 off-diagonal nonzero matrix entry A_ij (and its symmetric counterpart A_ji) is represented by the single edge (c_i, c_j) in E.

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 G_b = (V₁, V₂, E), a partial distance-2 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₁) is disjoint from the set of colors used for column vertices (V₂).

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.

Table 2: List of coloring problems for which implementations of algorithms are available in ColPack. The star coloring and star bicoloring problems have more than one algorithm implemented in ColPack.

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.

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, extensible and efficient.

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.

ColPack functions that a user needs to call directly are made available via the appropriate Interface classes.

Complete Doxygen documentation of ColPack