Abstract
Combinatorial scientific computing (CSC) is founded
on the recognition of the enabling power of combinatorial algorithms
in scientific and engineering computation and in highperformance computing.
The domain of CSC extends beyond traditional scientific computingthe
three major branches of which are numerical linear algebra,
numerical solution of differential equations, and
numerical optimizationto include a range of emerging and
rapidly evolving computational and information science disciplines.
Orthogonally, CSC problems could also emanate from
infrastructural technologies for supporting highperformance computing.
Despite the apparent disparity in their origins,
CSC problems and scenarios are unified by the following common features:
(A) The overarching goal is often to make computation
efficientby minimizing overall execution time, memory usage,
and/or storage spaceor to facilitate knowledge discovery or analysis.
(B) Identifying the most accurate combinatorial abstractions that
help achieve this goal is usually a part of the challenge.
(C) The abstractions are often expressed, with advantage, as graph
or hypergraph problems.
(D) The identified combinatorial problems are typically NPhard to
solve optimally. Thus, fast, often lineartime, approximation (or
heuristic) algorithms are the methods of choice.
(E) The combinatorial algorithms themselves often need to be
parallelized, to avoid their being bottlenecks within a larger
parallel computation.
(F) Implementing the algorithms and deploying them via software
toolkits is critical.
This talk attempts to illustrate the aforementioned features of CSC
through an example: we consider the enabling role graph coloring
models and their algorithms play in efficient computation of
sparse derivative matrices via automatic differentiation (AD).
The talk focuses on efforts being made on this topic within
the SciDAC Institute for Combinatorial Scientific Computing
and Petascale Simulations (CSCAPES).
Aiming at providing overview than details, we discuss
the various coloring models used in sparse Jacobian and Hessian computation,
the serial and parallel algorithms developed in CSCAPES
for solving the coloring problems, and a
case study that demonstrate the efficacy of the coloring techniques
in the context of an optimization problem in a Simulated Moving Bed process.
Implementations of our serial algorithms for the coloring
and related problems in derivative computation are assembled
and made publicly available in a package called ColPack.
Implementations of our parallel coloring algorithms are
incorporated into and deployed via the loadbalancing toolkit Zoltan.
ColPack has been interfaced with ADOLC, an operator overloadingbased
AD tool that has recently acquired improved capabilities for
automatic detection of sparsity patterns of Jacobians and Hessians
(sparsity pattern detection is the first step in derivative matrix
computation via coloringbased compression).
Further information on ColPack and Zoltan is available
at their respective websites, which can be accessed via
http://www.cscapes.org
BibTeX  Entry
@InProceedings{gebremedhin:DSP:2009:2093,
author = {Assefaw H. Gebremedhin},
title = {The Enabling Power of Graph Coloring Algorithms in Automatic Differentiation and Parallel Processing},
booktitle = {Combinatorial Scientific Computing},
year = {2009},
editor = {Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
number = {09061},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Schloss Dagstuhl  LeibnizZentrum fuer Informatik, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/2093},
annote = {Keywords: Graph coloring, sparse derivative computation, automatic differentiation, parallel computing}
}
Keywords: 

Graph coloring, sparse derivative computation, automatic differentiation, parallel computing 
Seminar: 

09061  Combinatorial Scientific Computing 
Issue Date: 

2009 
Date of publication: 

24.07.2009 