Home
Assefaw Gebremedhin, Research, Automatic Differentiation
Many algorithms for nonlinear optimization, solution of
differential equations, sensitivity analysis, and
uncertainity quantification rely on computation of derivatives.
Such algorithms
can greatly benefit from
Algorithmic (or Automatic) Differentiation (AD),
a technology for transforming a computer program for computing a function
into a program for computing the function's derivatives.
AD furnishes derivatives accurately (i.e. without truncation errors)
and with relatively little effort from a user's end, and the time and space complexity of
computing derivatives using AD can be bounded by
the complexity of evaluating the function itself. For these reasons,
AD is a better alternative to other methods
of computing derivatives such as finite differencing or symbolic differentiation,
or error-prone and tedious hand coding.
Reverse-mode based Hessian computation
Currently together with Mu Wang and Alex Pothen, I am working on new algorithms for
Hessian computation that aim at taking full advantage of the potential of
the Reverse-mode of AD and the symmetry available in the computational graph of
the Hessian.
Sparse computation via compression
Much of my previous work in Automatic Differentiation aimed at
exploiting the sparsity (and when applicable,
the symmetry) that is inherently available in large
derivative matrices -- Jacobians and Hessians -- in order to make their computation efficient in terms of runtime and memory requirement.
A fundamental technique that has proven effective in achieving
this objective is computation via compression.
Loosely speaking, the idea is to reduce
computational cost by calculating sums of columns
of a derivative matrix at a time instead of calculating one
column at a time.
Columns that are to be computed together are
determined by exploiting structural properties of the
matrix -- in particular, the structural information is used to partition
the set of columns into a small number of groups of
``independent'' columns. Here, a variety of matrix partitiong problems arise
depending on whether the matrix to be
computed is Jacobian (nonsymmetric) or Hessian (symmetric)
and the specifics of the computational approach taken.
Graph coloring models have proven to be a powerful tool
for analyzing the complexity of and designing effective algorithms
for these problems since the pioneering works of Coleman and
More in the early 1980s.
Papers
Below is a catalogued list of papers (recent ones listed first) I have written
together with a number of collaborators on graph-theoretic results and innovative
algorithms for (a) efficient Reverse-mode based Hessian computation and (b) matrix partitioning (coloring) and related problems in sparse derivative matrix computation.
Also incuded is information on the associated serial software package
ColPack
we developed in support of sparse derivative computation.
Reverse Mode-based Hessian computation
-
M. Wang, A.H. Gebremedhin and A. Pothen,
Capitalizing on Live Variables:
New Algorithms for Efficient Hessian Computation via
Automatic Differentiation,
Mathematical Programming Computation, Submitted, Nov 2014.
Abstract
Coloring and sparse derivative computation, sequential algorithms
-
A.H. Gebremedhin, D. Nguyen, M.M.A. Patwary and A. Pothen,
ColPack: Software for Graph Coloring and Related Problems in Scientific Computing,
ACM Transactions on Mathematical Software,
Vol 40, No 1, pp 1-31, 2013.
Abstract
Paper in PDF
-
A. Gebremedhin, A. Pothen, A. Tarafdar and A. Walther,
Efficient Computation of Sparse Hessians
Using Coloring and Automatic Differentiation, INFORMS Journal
on Computing, Vol 21, No 2, pp 209--223, 2009.
Abstract
Paper in PDF
-
A. Gebremedhin, A. Pothen and A.Walther, Exploiting Sparsity in Jacobian
Computation via Coloring and Automatic Differentiation: A Case Study in
a Simulated Moving Bed Process,
In C. Bischof et al. (Eds): Proc. of AD2008, Lecture Notes in
Computational Science and Engineering 64, pp 339-349, 2008, Springer.
.
Abstract
Paper in PDF
-
A. Gebremedhin, A. Tarafdar, F. Manne and A. Pothen, New Acyclic and
Star Coloring Algorithms with Applications to
Hessian Computation, SIAM Journal on
Scientific Computing, Vol 29, No 3, pp 1042--1072, 2007.
Abstract Paper
in PDF
-
A. Gebremedhin, F. Manne and A. Pothen, What Color Is Your Jacobian?
Graph Coloring for Computing Derivatives, SIAM Review, Vol 47, No
4, pp 629--705, 2005.
Abstract Paper
in PDF
Sparsity in Source to Source Transformation AD tools
-
S.H.K Narayanan, B. Norris, P. Hovland and A. Gebremedhin,
Implementation of Partial Separability in a Source to Source
Transformation AD Tool,
In S. Forth et al. (Eds.), Recent Advances in Algorithmic Differentiation,
Lecture Notes in Computational Science and Engineering 87, DOI 10.1007/978-3-642-30023-3_31,
2012, Springer.
Abstract
Paper in PDF
-
S.H.K Narayanan, B. Norris, P. Hovland, D. Nguyen and A. Gebremedhin,
Sparse Jacobian Computation using ADIC2 and ColPack,
Procedia Computer Science, 4:2115--2123, 2011.
Proceedings of the International Conference on Computational Science, ICCS 2011.
Abstract
Paper in PDF
Coloring and sparse derivative computation, parallel algorithms
-
B. Letschert, K. Kulshreshtha, A. Walther, D. Nguyen, A.H. Gebremedhin and A. Pothen,
Exploiting Sparsity in Automatic Differentiation on Multicore Architectures,
In S. Forth et al. (Eds.), Recent Advances in Algorithmic Differentiation,
Lecture Notes in Computational Science and Engineering 87, DOI 10.1007/978-3-642-30023-3_14, 2012, Springer.
Abstract
Paper in PDF
-
D. Bozdag, U. Catalyurek, A. Gebremedhin, F. Manne, E. Boman and F. Ozgunner,
Distributed-memory Parallel Algorithms for Distance-2 Coloring and
Related Problems in Derivative Computation,
SIAM Journal on Scientific Computing, Vol 32, Issue 4, pp 2418--2446, 2010.
Abstract
Paper in PDF
Software
ColPack is the name of our software package
comprising implementations of sequential algorithms for a variety of graph
coloring and related problems arising in sparse Jacobian and Hessian computation.
Many of the papers listed above, most notably the first paper, discuss the design, analysis, implementation,
and performance evaluation of the underlying coloring algorithms in ColPack.
In addition to coloring, ColPack has various routines for recovering the numerical
values of the entries of a derivative matrix from a compressed representation
as well as routines for constructing graph representations of Jacobians and Hessians
from sparsity patterns provided in various formats.
ColPack is written in C++ heavily using the Standard Template Library.
It is designed to be modular, extensible and efficient.
ColPack has been interfaced with the operator overloading based AD tool ADOL-C,
which is currently being developed and maintained at Paderborn University, Germany.
Recently, ColPack has also been interfaced with the source-to-source transformation
AD tool ADIC2, which is developed at Argonne National Laboratory.
The ColPack-AD toolkit is being used for end-to-end sparse derivative
computation, beginning with automatic detection of the sparsity pattern of
the derivative matrix of a function given as a computer program and ending
with the recovery of the entries of the original derivative matrix from its
compressed representation.
Examples of applications enabled by ColPack together with an AD tool include
Simulated Moving Bed optimization in chemical engineering and electric power flow
optimization.
ColPack is released for
free public use under the GNU Lesser General Public License. Versions subsequent to its first release feature added functionalities and improved performance (code optimizations).
For download and other more detailed information on ColPack, visit the
Software page.
Go back to Research Areas or
go side-ways to
Network Science
Parallel Algorithms
Parallel Computation Models