www.Autodiff.org - Publication: What Color Is Your Jacobian? Graph Coloring for Computing Derivatives

What Color Is Your Jacobian? Graph Coloring for Computing Derivatives

- Article in a journal -

Author(s)
Assefaw Hadish Gebremedhin , Fredrik Manne , Alex Pothen

Published in
SIAM Review

Year
2005

Publisher
SIAM

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.

AD Theory and Techniques
Sparsity

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 = "629-705",
       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 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."
}

back

autodiff.org
Username:
Password: