2026-08-17T23:44:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2093 2024-03-06T11:08:36Z ddc:004 open_access

The Enabling Power of Graph Coloring Algorithms in Automatic Differentiation and Parallel Processing Gebremedhin, Assefaw H. Graph coloring sparse derivative computation automatic differentiation parallel computing 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 Schloss Dagstuhl – Leibniz-Zentrum für Informatik Assefaw H. Gebremedhin 2009 Is Part Of Dagstuhl Seminar Proceedings, Volume 9061, Combinatorial Scientific Computing (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.09061.19 urn:nbn:de:0030-drops-20934 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09061.19 eng https://creativecommons.org/licenses/by/4.0/legalcode