Applications of a hyper-graph grammar system in adaptive finite-element computations

• Autorzy: Gurgul P. , Jopek K. , Pingali K. , Paszyńska A.

Identyfikatory

DOI

10.2478/amcs-2018-0044

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

adaptive finite element method; hypergraph grammar; mesh-based computations

PL

metoda elementów skończonych; gramatyka hipergrafu; siatka obliczeniowa

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2018
• Tom: Vol. 28, no. 3
• Strony: 569--582
• Opis fizyczny: Bibliogr. 25 poz., rys., wykr.

Twórcy

autor

Gurgul P.

• Dropbox Inc., 333 Brannan Street, San Francisco, CA 94107, USA

autor

Jopek K.

• Department of Computer Science, AGH University of Science and Technology, al. Mickiewicza 30, 30-059 Kraków, Poland

autor

Pingali K.

• Institute for Computational and Engineering Sciences, The University of Texas at Austin, Austin, TX 78712-1229, USA

autor

Paszyńska A.

• Faculty of Physics, Astronomy and Applied Computer Science, Jagiellonian University, ul. Łojasiewicza 11, 30-348 Kraków, Poland

Bibliografia

• [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.

Uwagi

PL

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).