Hypergraph grammar based multi-thread multi-frontal direct solver with Galois scheduler
Keywords:graph grammar, direct solver, $h$ adaptive finite element method, GALOIS
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.
Duff I. S., Reid J. K., The multifrontal solution of indefinite sparse symmetric linear systems. ACM Trans. on Math. Soft., 9 (1983) 302-325.
Duff I. S., Reid J. K., The multifrontal solution of unsymmetric sets of linear systems. SIAM Journal on Scientific and Statistical Computing, 5 (1984) 633-641.
Geng P., Oden T. J., van de Geijn R. A., A Parallel Multifrontal Algorithm and Its Implementation, Computer Methods in Applied Mechanics and Engineering, 149 (2006) 289-301.
Liu J., The role of elimination trees in sparse factorization, SIAM Journal of Matrix Analysis Applications, 11(1) (1990) 134-172.
Demkowicz L., Computing with hp adaptive finite element method. Part I. One and two dimensional elliptic and Maxwell problems, (2006) Chapmann & Hall / CRC Press.
V. Diekert, and G. Rozenberg, The book of traces, World Scientific Publishing (1995)
Schmitz P. G., Ying L., A fast direct solver for elliptic problems on general meshes in 2d. Journal of Computational Physics, 231 (2012) 1314-1338.
Paszynska A., Paszynski M., Grabska E. Graph transformations for modeling hp-adaptive finite element method with mixed triangular and rectangular elements. Lecture Notes in Computer Science, 5545 (2009) 875-884.
Paszynska A., Grabska E., Paszynski M., A Graph Grammar Model of the hp-Adaptive Three Dimensional Finite Element Method. Part I Fundamenta Informaticae 114 (2) (2012) 149-182
Paszynska A., Grabska E., Paszynski M., A Graph Grammar Model of the hp-Adaptive Three Dimensional Finite Element Method. Part II Fundamenta Informaticae 114 (2) (2012) 183-201.
Obrok P., Pierzchala P., Szymczak A., Paszynski M., Graph grammar-based multi-thread multi-frontal parallel solver with trace theory-based scheduler, Procedia Computer Science, 1(1) (2010) 1993-2001.
Paszynski M., Schaefer R., Graph Grammar Driven Parallel Partial Differential Equation Solver, Concurrency & Computations, Practise & Experience, 22(9) (2010) 1063-1097.
Pingali K., Nguyen D., Kulkarni K., Burtscher M., Hassaan M.A., Kaleem R., Lee T.-H. , Lenharth A., Manevich R., Mendez-Lojo M., Prountzos D., Sui X., The Tao of Parallelism in Algorithms, Proceedings of the 32nd ACM SIGPLAN conference on Programming language design and implementation (2011) 12-25.
MUlti-frontal Massively Parallel sparse direct Solver http://graal.enslyon.fr/MUMPS/
Paszynski M., On the parallelization of selfadaptive hp-finite element methods part I. composite programmable graph grammar model, Fundamenta Informaticae 93(4) (2009) 411434.
Paszynski M., On the parallelization of selfadaptive hp-finite element methods part II. Partitioning Communication Agglomeration Mapping (PCAM) Analysis, Fundamenta Informaticae 93(4) (2009) 435-457.
Slusarczyk, G. and Paszynska, A. Hypergraph grammars in hp-adaptive finite element method, Procedia Computer Science, (2012) 18, 1545–1554.