What Color is Your
Jacobian?
Graph Coloring for Computing Derivatives
Abstract.
Graph coloring has been
employed since the 1980s to efficiently compute sparse Jacobian and
Hessian matrices using either finite differences or automatic
differentiation. Several coloring problems occur in this context,
depending on whether the matrix is a Jacobian or a Hessian, and on the
specifics of the computational techniques employed. We consider eight
variant vertex coloring problems here. This article begins with a
gentle introduction to the problem of computing a sparse Jacobian,
followed by an overview of the historical development of the research
area. Then we present a unifying framework for the graph models of the
variant matrix estimation problems. The framework is based upon the
viewpoint that a partition of a matrix into structurally orthogonal
groups of columns corresponds to distance-2 coloring an appropriate
graph representation. The unified framework helps integrate earlier
work and leads to fresh insights; enables the design of more efficient
algorithms for many problems; leads to new algorithms for others; and
eases the task of building graph models for new problems. We report
computational results on two of the coloring problems to support our
claims. Most of the methods for these problems treat a column or a row
of a matrix as an atomic entity, and partition the columns or rows (or
both). A brief review of methods that do not fit these criteria is
provided. We also discuss results in discrete mathematics and
theoretical computer science that intersect with the topics considered
here.
Key
words. sparsity, symmetry,
Jacobians, Hessians, finite differences, automatic differentiation,
matrix partitioning problems, distance-k coloring, approximation
algorithms.
Full
paper in PDF
|
|