Hypergraph grammar based multi-thread multi-frontal direct solver with Galois scheduler

Abstract

In this paper, we analyze two-dimensional grids with point and edge singularities in order to develop an eficient parallel hypergraph grammar-based multi- frontal direct solver algorithm. We express these grids by a hypergraph. For these meshes, we define a sequence of hypergraph grammar productions expressing the construction of frontal matrices, eliminating fully assembled nodes, merging the resulting Schur complements, and repeating the process of elimination and merging until a single frontal matrix remains. The dependency relationship between hypergraph grammar productions is analyzed, and a dependency graph is plotted (which is equivalent to the elimination tree of a multi- frontal solver algorithm). We utilize a classical multi-frontal solver algorithm, the hypergraph grammar productions allow us to construct an eficient elimination tree based on the graph representation of the computational mesh (not the global matrix itself). The hypergraph grammar productions are assigned to nodes on a dependency graph, and they are implemented as tasks in the GALOIS parallel environment and scheduled according to the developed dependency graph over the shared memory parallel machine. We show that our hypergraph grammar-based solver outperforms the parallel MUMPS solver.