Using the Hypergraph Grammar for generation of quasi optimal element partition trees in two dimensions
Jakub Ryzner1, Maciej Paszyński2
, Anna Paszyńska3
1Faculty of Electrical Engineering, Automatics, Computer Science and Biomedical Engineering, AGH University of Science and Technology, Al. Mickiewicza 30, 30-059 Krakow, Poland.
2Department of Computer Science, AGH University of Science and Technology, Al. Mickiewicza 30, 30-059 Krakow, Poland.
3Faculty of Physics, Astronomy and Applied Computer Science, Jagiellonian University, ul. St. Łojasiewicza 11, 30-348 Krakow, Poland.
DOI:
https://doi.org/10.7494/cmms.2018.1.0611
Abstract:
The paper presents the graph grammar model of Finite Element Method allowing for speeding up performed numerical simulations. In the presented approach, the finite element mesh operations are performed together with operations generating so-called element partition tree. The element partition tree sets the ordering of matrix operations performed by solver in order to solve the computational problem. The quality of element partition tree influences the computational time of the solver. Our method allows for generation good quality element partition trees for h-adaptive Finite Element Method. The paper is concluded with numerical results confirming the quality of generated element partition trees.
Cite as:
Ryzner, J., Paszyński, M., Paszyńska, A. (2018). Using the Hypergraph Grammar for generation of quasi optimal element partition trees in two dimensions. Computer Methods in Materials Science, 18(1), 29 – 40. https://doi.org/10.7494/cmms.2018.1.0611
Article (PDF):
Keywords:
Finite element method, Multi-frontal solver, Hypergraph grammar
References:
Babuška, I., Rheinboldt, W., 1978, Error Estimates for Adaptive Finite Element Computations, SIAM Journal of Numerical Analysis, 15(4), 736-754.
Babuška, I., Szabo, B. A., Katz, I. N., 1981, The p-Version of the Finite Element Method, SIAM Journal on Nu-merical Analysis, 18, 515-545.
Babuška, I., 1986, Accuracy estimates and adaptive refine-ments in finite element computations, John Wiley and Sons.Banaś, K., Chłoń, K., Cybułka, P., Michalik, K., Płaszewski, P., Siwek, A, 2014, Adaptive finite element modelling of welding processes, Lecture Notes in Computer Sci-ence, 8500, 391-406.
Demkowicz, L., Pardo, D. , Rachowicz, W., 2002, 3D hp-Adaptive Finite Element Package (3Dhp90) Version 2.0. The Ultimate (?) Data Structure for Three-Dimen-sional Anisotropic hp-Renements, TICAM Report, 2-4.
Demkowicz, L., 2006, Computing with hp-Adaptive Finite Elements, Vol. I. One and Two Dimensional Elliptic and Maxwell Problems, Chapman and Hall/Crc Ap-plied Mathematics and Nonlinear Science.
Demkowicz, L., Kurtz, J., Paszyński, M, Rachowicz, W., Zdunek, A., 2006, Computing with hp-Adaptive Finite Elements, Vol. II. Frontiers: Three Dimensional Ellip-tic and Maxwell Problems with Applications, Chap-man and Hall/Crc Applied Mathematics and Nonlinear Science.
Duff, I. S., Reid, J. K., 1983, The multifrontal solution of indefinite sparse symmetric linear, ACM Trans. Math. Softw, 9(3), 302-325.
Duff, I. S., Reid, J. K., 1984, The multifrontal solution of unsymmetric sets of linear equations, Journal on Sci-entific and Statistical Computing, 5, 633-641.
Hughues, T., 2000, The Finite Element Method: Linear Static and Dynamic Finite Element Analysis, Dover Civil and Mechanical Engineering.Liu, J., 1990, The role of element partition trees in sparse factorization, SIAM Journal of Matrix Analysis Appli-cations, 11(1), 134-172.
METIS (n.d.). Metis – graph partitioning and fill-reducing matrix ordering, available online at: http://gl ros.dtc.umn.edu/gkhome/views/metis, accessed: 1.02.2018.
MUMPS (n.d.). Multi-frontal massively parallel sparse di-rect solver, available online at: http://mumps.en-seeiht.fr/, accessed: 1.02.2018.
Niemi, A., Babuška, I. , Pitkaranta, J., Demkowicz, L/, 2012, Finite element analysis of Girkmann problem using the modern hp-version and the classical h-version, Engi-neering with computers, 28(2), 123-134.
Pardo, D., Demkowicz, L., Torres-Verdin, C., Paszyński, M., 2006, Simulation of Resistivity Logging-While-Drilling (LWD) Measurements Using a Self-Adaptive Goal-Oriented hp-Finite Element Method, SIAM Jour-nal on Applied Mathematics, 66, 2085-2106.
Pardo, D., Calo, V. M., Torres-Verdin, C., Nam, M. J., 2008a, Fourier Series Expansion in a Non-Orthogonal System of Coordinates for Simulation of 3D DC Bore-hole Resistivity Measurements, Computer Methods in Applied Mechanics and Engineering, 197(1-3), 1906-1925.
Pardo, D., Torres-Verdin, C., Nam, M. J., Paszyński, M., Calo, V., 2008b, Fourier Series Expansion in a Non-Orthogonal System of Coordinates for the Simulation of 3D Alternating Current Borehole Resistivity Meas-urements, Computer Methods in Applied Mechanics and Engineering, 197(45-48), 3836-3849.
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, Quasi-optimal elemination trees for 2d grids with singularities, Scientific Programming, 1-18.
Paszyński, M., 2016, Fast Solvers for Mesh Based Compu-tations, Taylor & Francis, CRC Press.
Pingali, K., Nguyen, D., Kulkarni, K., Burtscher, M., Has-saan, M., Kaleem, R., Lee, T.-H., Lenharth, A., Ma-nevich, R., Mendez-Lojo, M., Prountzos, D., Sui, X., 2011, The tao of parallelism in algorithms, Proceed-ings of the 32nd ACM SIGPLAN conference on Pro-gramming language design and implementation, 12-25.
Ślusarczyk, G., Paszyńska, A., 2012, Hypergraph grammars in hp-adaptive finite element method, Procedia Com-puter Science, 18, 1545-1554.
Yannakakis, M., 1981, Computing the minimum fill-in is np-complete, SIAM Journal on Algebraic Discrete Methods, 2, 77-79.