LANS Informal Seminar: Assefaw Hadish Gebremedhin

Seminar Title: Algorithms and Software for Sparse Derivative Computation and Beyond
Speaker: Assefaw Hadish Gebremedhin, Research Assistant Professor, Department of Computer Science, Purdue University

Date/Time: 2010-12-01 15:00
Location: Bldg 240 Conference Center 1404-1405

Description:
We present a software package, called ColPack, encapsulating an array of fast and effective algorithms for a variety of graph coloring and associated problems arising in the efficient computation of large, sparse Jacobian and Hessian matrices using automatic differentiation. Several of the coloring problems supported by ColPack also find applications in many areas outside derivative computation; a few examples include: concurrency discovery in parallel computing, frequency assignment in wireless networks, scheduling, facility location, and compiler design. In this presentation, we will give an overview of the functionalities available in ColPack, describe the package’s major algorithms with a focus on the common framework within which they are designed, and present performance results, including comparisons of solutions yielded by the various coloring algorithms with appropriate lower bounds. As an example of an application that benefited from sparsity exploitation using ColPack, we will discuss a large-scale PDE-constrained optimization problem in a chromatographic separation process in chemical engineering. Finally, we will mention related efforts on the development of parallel algorithms for a subset of the coloring problems in ColPack.