A Graph-Grammar Based Multi-Frontal Parallel Direct Solver for One, Two and Three-Dimensional Partial Differential Equations

In this paper we present a new multi-frontal parallel direct solver algorithm for one, two and three dimensional finite difference method computations. The algorithm is dedicated for multi-core shared memory architecture. It is based on partitioning of the solver algorithm into multiple undividable tasks, expressed as graph grammar productions. The partial order of tasks is analyzed by introducing the dependency relations by means of the trace theory. The analysis implies the sequence of classes with independent tasks that can be executed in concurrent, one class after another. The algorithm involves also the minimization of memory usage for three dimensional problems by re-computing some branches of the elimination tree before the backward substitution. The solver has been implemented and tested on multi-core NVIDIA CUDA architecture.