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 efficient graph grammar based multi-frontal direct solver algorithm. We express these grids by hypergraph models. For these meshes we define a sequence of graph grammar productions expressing the construction of frontal matrices, elimination of fully assembled nodes, merging of resulting Schur complements, and repeating the process of elimination and merging until a single frontal matrix remains. The dependency relation between graph grammar productions is analyzed, and the dependency graph is plot, which is equivalent to the elimination tree of the multi-frontal solver algorithm. We utilize classical multi-frontal solver algorithm, and the graph grammar productions allows us to construct an efficient elimination tree, based on the graph representation of the computational mesh, and not the global matrix itself. The graph grammar productions are assigned to nodes of the dependency graph, and they are implemented as tasks in the GALOIS system and scheduled according to the developed dependency graph over the shared memory parallel machine. We show that our graph grammar based solver outperforms parallel MUMPS solver.