### Assefaw Gebremedhin, Research, Sparse Derivative Computation

Many algorithms for nonlinear optimization, solution of differential equations, sensitivity analysis, and uncertainity quantification rely on computation of derivatives. Algorithmic (or Automatic) Differentiation (AD) is a technology for transforming a computer program for computing a function into a program for computing the function's derivatives. A crux of AD is the systematic application of the chain-rule of calculus to the computer program specifying the function evaluation. Because AD furnishes derivatives accurately (i.e. without truncation errors) and with relatively little effort from a user's end and because the time and space complexity of computing derivatives using AD can be bounded by the complexity of evaluating the function itself, AD is superior to alternative methods of computing derivatives such as hand coding, finite differencing or symbolic differentiation.

The overall objective of much of my work in the area of derivative computation has been to exploit the sparsity (and when applicable, the symmetry) that is inherently available in large derivative matrices--Jacobians and Hessians--to make their computation via AD efficient in terms of runtime and memory requirement.

A fundamental technique that has proven effective in achieving this objective is computation via compression. Remarkably, the technique is equally well applicable to the case in which derivative matrices are computed (approximately) using finite differencing. 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. The specific criterion used to partition columns depends on three mutually orthogonal factors: whether the matrix being computed is Jacobian (nonsymmetric) or Hessian (symmetric); whether a unidirectional partition (involving only columns or rows) or a bidirectional partition (involving both columns or rows) is used; and whether the nonzero entries of the matrix are to be retrieved from its compressed representation directly (no additional arithmetic) or indirectly (via substitution). These three factors give rise to five different partitioning problems. 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.

Below is a list, in reverse chronological order, of papers I have written together with a number of collaborators on graph-theoretic results and innovative algorithms for these matrix partitioning (coloring) problems. Also incuded is information on the associated serial software package ColPack we developed.

Papers
• 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. Accepted.
Abstract

• 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

• 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

• 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

• 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

• 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

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 (see the second, fourth and fifth papers in the list above).

The first version of ColPack was released in October 2008 for free public use under the GNU Lesser General Public License. Newer versions with added functionalities and improved performance (code optimizations) have been released in a sequence of versions since then. For download and other more detailed information on ColPack, visit the colpack-download page.

Go back to Research Areas or go forward to
• Parallel Algorithms
• Parallel Computation Models