The Enabling Power of Graph Coloring Algorithms in Automatic Differentiation and Parallel Processing

Abstract

Combinatorial scientific computing (CSC) is founded 
on the recognition of the enabling power of combinatorial algorithms 
in scientific and engineering computation and in high-performance computing.
The domain of CSC extends beyond traditional scientific computing---the 
three major branches of which are numerical linear algebra, 
numerical solution of differential equations, and 
numerical optimization---to include a range of emerging and 
rapidly evolving computational and information science disciplines.
Orthogonally, CSC problems could also emanate from
infrastructural technologies for supporting high-performance 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  
  efficient---by minimizing overall execution time, memory usage, 
  and/or storage space---or 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 NP-hard to
  solve optimally.  Thus, fast, often linear-time, 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 load-balancing toolkit Zoltan. 
ColPack has been interfaced with ADOL-C, an operator overloading-based 
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 coloring-based compression).  
Further information on ColPack and Zoltan is available 
at their respective websites, which can be accessed via 
http://www.cscapes.org