Title: Graph Coloring Software for Computational Science and Engineering

Speaker: Assefaw Gebremedhin, Purdue University

Date/Time: Thursday, October 21, 2010, 9:00 am Mountain Time       

Location: CSRI Building/Room 90 (Sandia NM)

Brief Abstract: We present a software package, called ColPack, comprising an array of fast and effective algorithms for a variety of graph coloring and associated problems. Many of the supported problems arise in the efficient computation of large, sparse Jacobian and Hessian matrices using automatic differentiation via direct and indirect methods. Several of the coloring abstractions also find important applications in numerous areas outside derivative computation; a few examples include: concurrency discovery in parallel and distributed 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.  A part of the description of the algorithms will include a discussion of the theory and efficient implementation of a variety of vertex ordering techniques the coloring algorithms utilize. ColPack has been interfaced with the automatic differentiation tool ADOL-C, and the combined toolkit has enabled several large-scale applications. As one example, we will discuss how ColPack rendered feasible the solution of a large-scale PDE-constrained optimization problem in a chromatographic separation process in

Biography: Assefaw Gebremedhin is a Research Assistant Professor at the Department of Computer Science at Purdue University. His research interests include: combinatorial algorithms and their application to computational science and engineering and to information sciences; high-performance computing; and automatic differentiation. He has more than twenty peer-reviewed publications in scientific journals and conference proceedings. Assefaw received his PhD and MS in Computer Science from the University of Bergen, Norway, in 2003 and 1999, respectively, and his BS in Electrical Engineering from Addis Ababa University, Ethiopia, in 1992.

CSRI POC: Erik Boman, 844-2003