### LANS Publications

# "Combinatorial Algorithms for Computational Science and Engineering"

E. G. Boman, D. Bozdag, U. V. Catalyurek, K. D. Devine, A. H. Gebremedhin, P. D. Hovland, and A. Pothen

Preprint ANL/MCS-P1518-0708

Preprint Version: [pdf]

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.