Geodesic
Applications of a hyper-graph grammar system in adaptive finite-element computations
International Journal of Applied Mathematics and Computer Science, Tome 28 (2018) no. 3, pp. 569-582.

Voir la notice de l'article provenant de la source Library of Science

This paper describes application of a hyper-graph grammar system for modeling a three-dimensional adaptive finite element method. The hyper-graph grammar approach allows obtaining a linear computational cost of adaptive mesh transformations and computations performed over refined meshes. The computations are done by a hyper-graph grammar driven algorithm applicable to three-dimensional problems. For the case of typical refinements performed towards a point or an edge, the algorithm yields linear computational cost with respect to the mesh nodes for its sequential execution and logarithmic cost for its parallel execution. Such hyper-graph grammar productions are the mathematical formalism used to describe the computational algorithm implementing the finite element method. Each production indicates the smallest atomic task that can be executed concurrently. The mesh transformations and computations by using the hyper-graph grammar-based approach have been tested in the GALOIS environment. We conclude the paper with some numerical results performed on a shared-memory Linux cluster node, for the case of three-dimensional computational meshes refined towards a point, an edge and a face.
Keywords: adaptive finite element method, hypergraph grammar, mesh-based computations
Mots-clés : metoda elementów skończonych, gramatyka hipergrafu, siatka obliczeniowa 
@article{IJAMCS_2018_28_3_a12,
     author = {Gurgul, P. and Jopek, K. and Pingali, K. and Paszy\'nska, A.},
     title = {Applications of a hyper-graph grammar system in adaptive finite-element computations},
     journal = {International Journal of Applied Mathematics and Computer Science},
     pages = {569--582},
     publisher = {mathdoc},
     volume = {28},
     number = {3},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IJAMCS_2018_28_3_a12/}
}
TY  - JOUR
AU  - Gurgul, P.
AU  - Jopek, K.
AU  - Pingali, K.
AU  - Paszyńska, A.
TI  - Applications of a hyper-graph grammar system in adaptive finite-element computations
JO  - International Journal of Applied Mathematics and Computer Science
PY  - 2018
SP  - 569
EP  - 582
VL  - 28
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IJAMCS_2018_28_3_a12/
LA  - en
ID  - IJAMCS_2018_28_3_a12
ER  - 
%0 Journal Article
%A Gurgul, P.
%A Jopek, K.
%A Pingali, K.
%A Paszyńska, A.
%T Applications of a hyper-graph grammar system in adaptive finite-element computations
%J International Journal of Applied Mathematics and Computer Science
%D 2018
%P 569-582
%V 28
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IJAMCS_2018_28_3_a12/
%G en
%F IJAMCS_2018_28_3_a12
Gurgul, P.; Jopek, K.; Pingali, K.; Paszyńska, A. Applications of a hyper-graph grammar system in adaptive finite-element computations. International Journal of Applied Mathematics and Computer Science, Tome 28 (2018) no. 3, pp. 569-582. http://geodesic.mathdoc.fr/item/IJAMCS_2018_28_3_a12/

[1] Aboueisha, H., Calo, V.M., Jopek, K., Moshkov, M., Paszyńska, A., Paszyński, M. and Skotniczny, M. (2017). Element partition trees for h-refined meshes to optimize direct solver performance. Part I: Dynamic programming, International Journal of Applied Mathematics and Computer Science 27(2): 351–365, DOI: 10.1515/amcs-2017-0025.

[2] Bao, G., Hu, G. and Liu, D. (2012). An h-adaptive finite element solver for the calculations of the electronic structures, Journal of Computational Physics 231(14): 4967–4979.

[3] Belytschko, T. and Tabbar, M. (1993). h-adaptive finite element methods for dynamic problems, with emphasis on localization, International Journal for Numerical Methods in Engineering 36(24): 4245–4625.

[4] Duff, I.S. and Reid, J.K. (1983). The multifrontal solution of indefinite sparse symmetric linear, ACM Transactions on Mathematical Software 9(3): 302–325.

[5] Duff, I.S. and Reid, J.K. (1984). The multifrontal solution of unsymmetric sets of linear equations, SIAM Journal on Scientific and Statistical Computing 5(3): 633–641.

[6] Flasiński, M. and Schaefer, R. (1996). Quasi context sensitive graph grammars as a formal model of FE mesh generation, Computer-Assisted Mechanics and Engineering Science 3: 191–203.

[7] Goik, D., Paszyński, M., Lenharth, A., Nguyen, D. and Pingali, K. (2014). Graph grammar based multi-thread multi-frontal direct solver with Galois scheduler, Procedia Computer Science 29: 960–969.

[8] Grabska, E. (1993a). Theoretical concepts of graphical modeling. Part I: Realization of CP-graphs, Machine Graphics and Vision 1(2): 3–38.

[9] Grabska, E. (1993b). Theoretical concepts of graphical modeling. Part II: CP-graph grammars and languages, Machine Graphics and Vision 2(2): 149–178.

[10] Habel, A. and Kreowski, H.J. (1987a). May we introduce to you: Hyperedge replacement, in H. Ehrig et al. (Eds.), Graph-Grammars and Their Application to Computer Science, Lecture Notes in Computer Science, Vol. 291, Springer, Berlin/Heidelberg, pp. 5–26.

[11] Habel, A. and Kreowski, H.J. (1987b). Some structural aspects of hypergraph languages generated by hyperedge replacement, in F.J. Brandenburg et al. (Eds.), STACS 87, Lecture Notes in Computer Science, Vol. 247, Springer, Berlin/Heidelberg, pp. 207–219.

[12] Irons, B.M. (1970). A frontal solution program for finite-element analysis, International Journal for Numerical Methods in Engineering 2: 5–32.

[13] Karypis, G. and Kumar, V. (2009). MeTis: Unstructured Graph Partitioning and Sparse Matrix Ordering System, Version 4.0, http://www.cs.umn.edu/˜metis.

[14] Paszyńska, A., Grabska, E. and Paszyński, M. (2012a). A graph grammar model of the hp adaptive three dimensional finite element method, Part I, Fundamenta Informaticae 114(2): 149–182.

[15] Paszyńska, A., Grabska, E. and Paszyński, M. (2012b). A graph grammar model of the HP adaptive three dimensional finite element method, Part II, Fundamenta Informaticae 114(2): 183–201.

[16] Paszyńska, A., Paszyński, M. and Grabska, E. (2009). Graph transformations for modeling hp-adaptive finite element method with mixed triangular and rectangular elements, in G. Allen et al. (Eds.), ICCS 2009, Lecture Notes in Computer Science, Vol. 5545, Springer, Berlin/Heidelberg, pp. 875–884.

[17] Paszyńska, A., Paszyński, M., Jopek, K., Woźniak, M., Goik, D., Gurgul, P., AbouEisha, H., Moshkov, M., Calo, V.M., Lenharth, A., Nguyen, D. and Pingali, K. (2015). Quasi-optimal elimination trees for 2D grids with singularities, Scientific Programming 2015, Article ID: 303024, DOI:10.1155/2015/303024.

[18] Paszyński, M. (2009). On the parallelization of self-adaptive hp-finite element methods, Part I: Composite programmable graph grammar model, Fundamenta Informaticae 4(93): 411–434.

[19] Paszyński, M. (2016). Fast Solvers for Mesh-Based Computations, CRC Press, Boca Raton, FL.

[20] Paszyński, M. and Paszyńska, A. (2008). Graph transformations for modeling parallel hp-adaptive finite element method, in R. Wyrzykowski et al. (Eds.), PPAM 2007, Lecture Notes in Computer Science, Vol. 4967, Springer, Berlin/Heidelberg, pp. 1313–1322.

[21] Paszyński, M. and Schaefer, R. (2010). Graph grammar-driven parallel partial differential equation solver, Concurrency and Computation Practice and Experience 22: 1063–1097.

[22] Pingali, K., Nguyen, D., Kulkarni, K., Burtscher, K.M., Hassaan, M.A., Kaleem, R., Lee, T.-H., Lenharth, A., Manevich, R., Mendez-Lojo, M., Prountzos, D. and Sui, X. (2011). The Tao of parallelism in algorithms, 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation, San Jose, CA, USA, pp. 12–22.

[23] Ryszka, I., Paszyńska, A., Grabska, E., Sieniek, M. and Paszyński, M. (2015a). Graph transformation systems for modeling three dimensional finite element method, Part I, Fundamenta Informaticae 140(2): 129–172.

[24] Ryszka, I., Paszyńska, A., Grabska, E., Sieniek, M. and Paszyński, M. (2015b). Graph transformation systems for modeling three dimensional finite element method, Part II, Fundamenta Informaticae 140(2): 173–203.

[25] Ślusarczyk, G. and Paszyńska, A. (2013). Hypergraph grammars in hp-adaptive finite element method, Procedia Computer Science 18: 1545–1554.