BibTeX
@ARTICLE{
Gebremedhin2005WCI,
author = "Assefaw Hadish Gebremedhin and Fredrik Manne and Alex Pothen",
title = "What Color Is Your {J}acobian? Graph Coloring for Computing Derivatives",
publisher = "SIAM",
year = "2005",
journal = "SIAM Review",
volume = "47",
number = "4",
pages = "629705",
url = "http://link.aip.org/link/?SIR/47/629/1",
doi = "10.1137/S0036144504444711",
ad_theotech = "Sparsity",
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 distance2 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."
}
