Argonne National Laboratory

Combinatorial Algorithms for Computational Science and Engineering

TitleCombinatorial Algorithms for Computational Science and Engineering
Publication TypeConference Paper
Year of Publication2007
AuthorsBoman, EG, Bozdag, D, Catalyurek, UV, Devine, KD, Gebremedhin, AH, Hovland, PD, Pothen, A
Date Published12/2007
Other NumbersANL/MCS-P1518-0708

CSCAPES was established in 2006 to help contribute to the SciDAC mission by developing infrastructural algorithmic and software technologies for supporting highperformance computing. Its scope encompasses four areas: load-balancing and related tasks in parallel processing (such as data migration and task scheduling); automatic
differentiation (AD), a technology for transforming computer source code for computing a function into code for computing its derivatives; basic ingredients in linear solver technology; and runtime data and iteration reordering to improve performance in irregular computation.
The focus in CSCAPES in each of these areas is on the formulation (modeling) and solution (algorithms) of the underlying fundamental combinatorial problems, which are often phrased using graphs or hypergraphs. Load-balancing, the task of distributing data and work in a largescale computation among the processors of a machine to minimize total execution time, can be phrased as a partitioning problem on a graph, or with more accuracy, on a hypergraph. When computational dependency among subtasks is modeled using a graph, a distance-1 coloring of the graph can be used to determine a scheduling of the tasks for concurrent computation. Distance-2 coloring and several other specialized variants are used to model matrix partitioning
problems that arise in the efficient computation of sparse Jacobians and Hessians using AD. In AD, exploitation of associativity and commutativity in the chain rule of differential calculus leads to a variety of vertex or edge elimination problems in the directed acyclic graph used to represent the computation of a function and its derivative. Various types of matchings in graphs are used in the solution of sparse linear systems (numerical preprocessing and block triangular decomposition) and in the coarsening phase of multilevel methods for graph partitioning. Work and storage reduction in direct solvers for large sparse systems calls for vertex ordering problems
in graphs. Graph and hypergraph based models are used to capture the needs in reordering the nodes and elements within an unstructured mesh to improve runtime performance.