Using the System of Graph Grammar for generation of quasi optimal element partition trees in two dimensions
Anna Paszyńska1
, Iwona Świderska1, Maciej Woźniak2, Konrad Jopek2, Maciej Paszyński2, Ewa Grabska1, Andrew Lenhart3, Donals Nguyen3, Keshav Pingali3
1Faculty of Physics, Astronomy and Applied Computer Science, Jagiellonian University, ul. St. Łojasiewicza 11, 30-348 Krakow, Poland.
2Department of Computer Science, AGH University of Science and Technology, Al. Mickiewicza 30, 30-059 Cracow, Poland.
3Institute for Computational and Engineering Science, The University of Texas in Austin, USA.
DOI:
https://doi.org/10.7494/cmms.2016.3.0583
Abstract:
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.
Cite as:
Paszyńska, A., Świderska, I., Woźniak, M., Jopek, K., Paszyński, M., Grabska, E., Lenhart, A., Nguyen, D., Pingali, K. (2016). Using the System of Graph Grammar for generation of quasi optimal element partition trees in two dimensions. Computer Methods in Materials Science, 16(3), 143 – 155. https://doi.org/10.7494/cmms.2016.3.0583
Article (PDF):
Keywords:
Graph grammar, Automatic hp adaptivity, Finite Element Method, optimal element partition tree, Multifrontal solver
References:
Demkowicz, L., 2006, Computing with hp-Adaptive FiniteElements, vol. I. One and Two Dimensional Elliptic andMaxwell Problems, Chapman and Hall / CRC Press,New York.
Duff, I. S., Reid, J. K., 1983, The multifrontal solution of indefinitesparse symmetric linear, ACM Trans. Math. Softw,9(3), 302-325.
Duff, I. S., Reid, J. K., 1984, The multifrontal solution of unsymmetricsets of linear equations, Journal on Scientificand Statistical Computing 5, 633-641.
GEF, 2016, Graphical editing framework for eclipse, availableonline at: http://www.eclipse.org/gef, accessed:23.10.2016.
Geng, P., Oden, T. J. van de Geijn, R. A., 2006, A parallel multifrontalalgorithm and its implementation, ComputerMethods in Applied Mechanics and Engineering, 149,289-301.
JUNG, 2016, Java universal network/graph framework, availableonline at: http://jung.sourceforge.net/, 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 matrixordering, available online at: http://glaros.dtc.umn.edu/gkhome/views/metis, 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, I., Grabska, E., 2015, A graph grammar toolfor generating computational grid structures, Proceedingsof the Artificial intelligence and soft computingConference, 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., Calo, V.M., Lenharth, A., Nguyen, D., Pingali, K., 2015, Quasioptimalelemination 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 YorkPaszyński, M. Schaefer, R., 2010, Graph grammar driven parallelpartial differential equation solver, Concurrency &Computations,Practise & Experience, 22(9), 1063-1097.
Pilat, A., 2004, Femlab software applied to active magneticbearing analysis, International Journal of Applied Mathematicsand Computer Science, 14(4), 497-501.
Pingali, K., Nguyen, D., Kulkarni, K., Burtscher, M., Hassaan,M., Kaleem, R., Lee, T.-H., Lenharth, A., Manevich, R.,Mendez-Lojo, M., Prountzos, D. Sui, X., 2011, The taoof parallelism in algorithms, Proceedings of the 32ndACM SIGPLAN Conference on Programming languagedesign 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 modelingthree dimensional finite element method. part ii, FundamentaInformaticae, 2, 173-203.
Ślusarczyk, G. Paszyńska, A., 2013, Hypergraph grammars inhp-adaptive finite element method, Procedia ComputerScience, 18, 1545-1554.
Strug, B., Paszyńska, A., Paszyński, M. Grabska, E., 2013,.Hypergraph grammars in hp-adaptive finite elementmethod, International Journal of Applied Mathematicsand Computer Science, 23(4), 839-853.
ZEST, 2016, The eclipse visualization toolkit, Available onlineat: http://www.eclipse.org/gef/zest accessed: 23.10.2016.