Using the system of graph grammar for generation of quasi optimal element partition trees in two dimensions

• Autorzy: Paszyńska A. , Świderska I. , Woźniak M. , Jopek K. , Paszyński M. , Grabska E. , Lenhart A. , Nguyen D. , Pingali K.

Warianty tytułu

Zastosowanie systemu gramatyk grafowych do generacji quasi-optymanych drzew podziałów siatki w dwóch wymiarach

• Języki publikacji: EN

Abstrakty

EN

The paper presents a graph grammar based approach for h-adaptive finite element method and multi-frontal solver algorithm. The multi-frontal solver is used for solving systems of linear equations created by finite element method. The multi-frontal solver is controlled by so-called ordering. The quality of ordering influences hardly the solver effectiveness. In our approach, the finite element mesh is represented by means of a hypergraph and corresponding element partition tree. The finite element operations like mesh generation or h-adaptation are modelled by graph grammar production. Additionally graph grammar productions have corresponding productions for the construction of the element partition tree. The element partition trees are transformed into the ordering that controlls execution of the solver algorithm. We show that the ordering resulting from our element partititon tree results in better performance of the parallel solver than the state of the art nested-dissection ordering available through MUMPS interface on the class of grids refined towards singularities.

PL

W artykule tym prezentujemy gramatykę grafową do modelowania algorytmów h adaptacyjnej metody elementów skończonych oraz solwera wielofrontalncgo. Solwer wielofronatlny używany jest do rozwiązania układu równań liniowych stworzonych przez metodę elementów skończonych. Solwer ten kontrolowany jest przez tak zwany porządek eliminacji. Jakość porządku eliminacji wpływa na efektywność solwera wielofrontalnego. W naszym podejściu siatka metody elementów skończonych reprezentowana jest przez hipergraf oraz związane z nim drzewo podziałów siatki. Operacje na elementach skończonych takie jak generacja siatki oraz h adaptacja modelowane są przez produkcję gramatyki grafowej. Dodatkowo, gramatyka grafowa posiada powiązane produkcje do generacji drzewa podziałów siatki. Drzewo podziałów siatki z kolei transformowane jest w porządek eliminacji, który kontroluje wykonanie algorytmu solwera. Pokazujemy że porządek eliminacji uzyskany na podstawie naszego drzewa podziałów siatki daje lepszą wydajność algorytmu solwera równoległego w porównaniu z klasycznym porządkiem nested- disseetions dostępnym w solwerze MUMPS, dla klas siatek adaptowalnych do lokalnych osobliwości.

Słowa kluczowe

EN

graph grammar; automatic hp adaptivity; finite element method; multi-frontal solver; optimal element partition tree

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Methods in Materials Science
• Rocznik: 2016
• Tom: Vol. 16, No. 3
• Strony: 143--155
• Opis fizyczny: Bibliogr. 19 poz., rys.

Twórcy

autor

Paszyńska A.

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

autor

Świderska I.

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

autor

Woźniak M.

• Department of Computer Science, AGH University of Science and Technology, Al. Mickiewicza 30, 30-059 Cracow, Poland

autor

Jopek K.

• Department of Computer Science, AGH University of Science and Technology, Al. Mickiewicza 30, 30-059 Cracow, Poland

autor

Paszyński M.

• Department of Computer Science, AGH University of Science and Technology, Al. Mickiewicza 30, 30-059 Cracow, Poland

autor

Grabska E.

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

autor

Lenhart A.

• Institute for Computational and Engineering Science, The University of Texas in Austin, USA

autor

Nguyen D.

• Institute for Computational and Engineering Science, The University of Texas in Austin, USA

autor

Pingali K.

• Institute for Computational and Engineering Science, The University of Texas in Austin, USA

Bibliografia

• Demkowicz, L., 2006, Computing with hp-Adaptive Finite Elements, vol. I. One and Two Dimensional Elliptie and Maxwell Problems, Chapman and Hall / CRC Press, New York.
• Duff, I. S., Reid, J. K., 1983, The multifrontal solution of indefinite sparse symmetric linear, ACM Trans. Math. Soflw, 9(3), 302-325.
• Duff, I. S., Reid, J. K., 19X4, The multifrontal solution of unsymmetrie sets of linear equations, .Journal on Scientific and Statistical Computing 5, 633-641.
• GEF, 2016, Graphical editing framework for eclipse, available online at:http://www.eelipse.org/gef, accessed:23.10.2016.
• Geng, P., Oden, T. J. van de Geijn, R. A., 2006, A parallel multifrontal algorithm and its implementation, Computer Methods in Applied Mechanics and Engineering, 149, 289-301.
• JUNG, 2016, Java universal network/graph framework, available online at: http://jung.sourccforge.nct/, accessed:23.10.2016.
• Liu, J., 1990, The role of element partition trees in sparse factorization, SIAM Journal of Matrix Analysis Applications, 11(1), 134-172.
• METIS, Metis - graph partitioning and fill-reducing matrix ordering, available online at: http://glaros.dtc.umn.edu/ gkhomc/vicws/mctis, accessed: 23.10.2016.
• MUMPS, Multi-frontal massively parallel sparse direct solver, available online at: http://mumps.enseeiht.fr/, accessed:23.10.2016.
• Palacz,W., Ryszka, L, Grabska, 0., 2015, A graph grammar tool for generating computational grid structures, Proceedings of the Artificial intelligence and soft computing Conference, eds, Rutkowski, L., Korytkowski, M., Scherer, R., Tadeusiewicz, R., Zadeh, L., Zurada, J., ICAISC 2015, Zakopane, Poland, 436-447.
• Paszyńska, A., Paszyński, M., Jopek, K., Woźniak, M., Goik, D., Gurgul, P., AbouEisha, P., Moshkov, M., Cało, V. M., Lcnharth, A., Nguyen, D., Pingali, K., 2015, Quasi-optimal elemination trees for 2d grids with singularities. Scientific Programming, article ID 303024, 1-18.
• Paszyński, M., 2016, Fast Solvers for Mesh Based Computations, Taylor & Francis, CRC Press., New York
• Paszyński, M. Schaefer, R., 2010, Graph grammar driven parallel partial differential equation solver. Concurrency A Computations,Practise & Experience, 22(9), 1063-1097.
• Pilat, A., 2004, Femlab software applied to active magnetic bearing analysis. International Journal of Applied Mathematics and Computer Science, 14(4), 497-501.
• Pingali, K., Nguyen, IX, Kulkami, K., Burtscher, M., Hassaan, M.. Kalccm, R., Lee, T.-IL, Lenharth, A., Manevich, R., Mendez-Lojo, M., Prountzos, I). Sui, X., 2011, flic tao of parallelism in algorithms. Proceedings of the 32nd ACM SIGPLAN Conference on Programming language design and implementation, eds Mary Hall, David Padua, 12-25.
• Ryszka, I., Paszyńska, A., Grabska, E., Sieniek, M. Paszyński, M., 2015,. Graph transformation systems for modeling three dimensional finite element method, part ii. Fundamenta Informaticae, 2, 173-203.
• Ślusarczyk, G. Paszyńska, A., 2013, Hypergraph grammars in lip-adaptive finite element method, Procedia Computer Science, 18, 1545-1554.
• Strug, B., Paszyńska, A., Paszyński, M. Grabska, E., 2013,. Hypergraph grammars in lip-adaptive finite element method. International Journal of Applied Mathematics and Computer Science, 23(4), 839-853.
• ZEST, 2016, The eclipse visualization toolkit. Available online at: http://www.eclipse.org/gef/zest accessed: 23.10.2016

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).