Seminar Details:

LANS Informal Seminar
"Algorithms and Software for Sparse Derivative Computation and Beyond"

DATE: December 1, 2010

TIME: 15:00:00 - 16:00:00
SPEAKER: Assefaw Hadish Gebremedhin, Research Assistant Professor, Department of Computer Science, Purdue University
LOCATION: Bldg 240 Conference Center 1404-1405, Argonne National Laboratory

[related website]

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.


Please send questions or suggestions to Debojyoti Ghosh: ghosh at mcs dot anl dot gov.