Professor Assefaw Gebremedhin
College of Science

Graph Algorithms for Sparse Derivative Computation

ABSTRACT

 Many algorithms for solving nonlinear optimization problems and differential equations, and methods for uncertainty quantification and sensitivity analysis need to evaluate Jacobian and Hessian matrices, first and second order derivative matrices, respectively. Computations that rely on derivatives are being empowered by Automatic Differentiation (AD), a chain-rule based technology for computing derivatives of mathematical functions specified by computer programs. Derivative matrices that arise in large-scale applications are sparse. I will present graph-coloring models, algorithms and software that we have developed to exploit sparsity and make large-scale Jacobian and Hessian computation via AD efficient in terms of execution time and memory requirement. Our software (ColPack) is coupled with the AD software tool ADOL-C, and the combined toolkit has enabled several applications. As an example, I will show how the toolkit is used to efficiently compute large Jacobians in the context of an optimization problem in a chromatographic separation process. Finally, I will highlight some of our work on the design of scalable graph algorithms on high-performance computing platforms.

 AUTHOR BIO

 Assefaw Gebremedhin is a Research Assistant Professor at the Department of Computer Science at Purdue University. His research interests include: combinatorial scientific computing, high-performance computing, and optimization.  He is a founding member and a co-investigator in the Combinatorial Scientific Computing and Petascale Simulations (CSCAPES) Institute, a multi-institution project funded for 2006--12 by the Department of Energy under the SciDAC-2 program.  Assefaw received his PhD and MSc in Computer Science from the University of Bergen, Norway, and his BSc in Electrical Engineering from Addis Ababa University, Ethiopia.