Element partition trees for h-refined meshes to optimize direct solver performance. Part I: Dynamic programming

• Autorzy: Aboueisha H. , Calo V. M. , Jopek K. , Moshkov M. , Paszyńska A. , Paszyński M. , Skotniczny M.

Identyfikatory

DOI

10.1515/amcs-2017-0025

• Języki publikacji: EN

Abstrakty

EN

We consider a class of two- and three-dimensional h-refined meshes generated by an adaptive finite element method. We introduce an element partition tree, which controls the execution of the multi-frontal solver algorithm over these refined grids. We propose and study algorithms with polynomial computational cost for the optimization of these element partition trees. The trees provide an ordering for the elimination of unknowns. The algorithms automatically optimize the element partition trees using extensions of dynamic programming. The construction of the trees by the dynamic programming approach is expensive. These generated trees cannot be used in practice, but rather utilized as a learning tool to propose fast heuristic algorithms. In this first part of our paper we focus on the dynamic programming approach, and draw a sketch of the heuristic algorithm. The second part will be devoted to a more detailed analysis of the heuristic algorithm extended for the case of hp-adaptive grids.

Słowa kluczowe

EN

h-adaptive finite element method; ordering; element partition tree; extensions of dynamic programming; multifrontal direct solvers

PL

metoda elementów skończonych; porządkowanie danych; programowanie dynamiczne

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2017
• Tom: Vol. 27, no. 2
• Strony: 351--365
• Opis fizyczny: Bibliogr. 31 poz., rys., tab.

Twórcy

autor

Aboueisha H.

• Computer, Electrical and Mathematical Sciences and Engineering (CEMSE), King Abdullah University of Science and Technology, Bld. 1 (Al-khawarizmi), 4128-WS03, Thuwal, 23955-6900, Kingdom of Saudi Arabia

autor

Calo V. M.

• Faculty of Science and Engineering, Western Australian School of Mines, Curtin University, Kent Street, Perth, WA 6102, Australia

autor

Jopek K.

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

autor

Moshkov M.

• Computer, Electrical and Mathematical Sciences and Engineering (CEMSE), King Abdullah University of Science and Technology, Bld. 1 (Al-khawarizmi), 4128-WS03, Thuwal, 23955-6900, Kingdom of Saudi Arabia

autor

Paszyńska A.

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

autor

Paszyński M.

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

autor

Skotniczny M.

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

Bibliografia

• [1] AbouEisha, H., Calo, V.M., Jopek, K.,Moshkov, M., Paszyńska, A., Paszyński, M. and Skotniczny, M. (2016). Element partition trees for two- and three-dimensional h-refined meshes and their use to optimize direct solver performance. Part II: Heuristic algorithms, Journal of Computational and Applied Mathematics, (submitted).
• [2] AbouEisha, H., Gurgul, P., Paszyńska, A., Paszyński, M., Kuźnik, K. and Moshkov, M. (2015). An automatic way of finding robust elimination trees for a multi-frontal sparse solver for radical 2D hierarchical meshes, in R. Wyrzykowski et al. (Eds.), Parallel Processing and Applied Mathematics, Lecture Notes in Computer Science, Vol. 8385, Springer, Berlin/Heidelberg, pp. 531–540.
• [3] AbouEisha, H., Moshkov, M. Calo, V.M., Paszyński, M., Goik, D. and Jopek, K. (2014). Dynamic programming algorithm for generation of optimal elimination trees for multi-frontal direct solver over h-refined grids, Procedia Computer Science 29: 947–959.
• [4] Amestoy, P.R., Davis, T.A. and Du, I.S. (1996). An approximate minimum degree ordering algorithm, SIAM Journal of Matrix Analysis & Application 17(4): 886–905.
• [5] Amestoy, P.R., Duff, I.S. and L’Excellent, J.-Y. (2000). Multifrontal parallel distributed symmetric and unsymmetric solvers, Computer Methods in Applied Mechanics and Engineering 184(2): 501–520.
• [6] Amestoy, P.R., Duff, I.S., L’Excellent, J.-Y. and Koster, J. (2001). A fully asynchronous multifrontal solver using distributed dynamic scheduling, SIAM Journal on Matrix Analysis and Applications 23(1): 15–41.
• [7] Amestoy, P.R., Guermouche, A., L’Excellent, J.-Y. and Pralet, S. (2006). Hybrid scheduling for the parallel solution of linear systems, Parallel Computing 32(2): 136–156.
• [8] Babuška, I. and Rheinboldt, W.C. (1978). Error estimates for adaptive finite element computations, SIAM Journal of Numerical Analysis 15(4): 736–754.
• [9] 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.
• [10] Barboteu, M., Bartosz, B. and Kalita, P. (2013). An analytical and numerical approach to a bilateral contact problem with nonmonotone friction, International Journal of Applied Mathematics and Computer Science 23(2): 263–276, DOI: 10.2478/amcs-2013-0020.
• [11] Becker, R., Kapp, H. and Rannacher, R. (2000). Adaptive finite element methods for optimal control of partial differential equations: Basic concept, SIAM Journal on Control and Optimisation 39(1): 113–132.
• [12] 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–4265.
• [13] Demkowicz, L. (2006). Computing with hp-Adaptive Finite Elements, Vol. I: One and Two Dimensional Elliptic and Maxwell Problems, Chapman and Hall/CRC, Boca Raton, FL.
• [14] Duff, I.S., Erisman, A.M. and Reid, J.K. (1986). Direct Methods for Sparse Matrices, Oxford University Press, Oxford.
• [15] 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.
• [16] Duff, I.S. and Reid, J.K. (1984). The multifrontal solution of unsymmetric sets of linear equations, SIAMJournal on Scientific and Statistical Computing 5(3): 633–641.
• [17] Errikson, K. and Johnson, C. (1991). Adaptive finite element methods for parabolic problems. I: A linear model problem, SIAM Journal on Numerical Analysis 28(1): 43–77.
• [18] Fiałko, S. (2009a). A block sparse shared-memory multifrontal finite element solver for problems of structural mechanics, Computer Assisted Mechanics and Engineering Science 16: 117–131.
• [19] Fiałko, S. (2009b). The block subtracture multifrontal method for solution of large finite element equation sets, Technical Transactions 8: 175–188.
• [20] Fiałko, S. (2010). PARFES: A method for solving finite element linear equations on multi-core computers, Advanced Engineering Software 40(12): 1256–1265.
• [21] Hughues, T. (2000). The Finite Element Method: Linear Static and Dynamic Finite Element Analysis, Dover, New York, NY.
• [22] Karczewska, A., Rozmej, P., Szczeciński, M. and Boguniewicz, B. (2016). A finite element method for extended KdV equations, International Journal of Applied Mathematics and Computer Science 26(3): 555–567, DOI: 10.1515/amcs-2016-0039.
• [23] Kardani, M., Nazem, M., Abbo, A.J., Sheng, D. and Sloan, S.W. (2012). Refined h-adaptive finite element procedure for large deformation geotechnical problems, Computational Mechanics 49(1): 21–33.
• [24] Karypis, G. and Kumar, V. (1999). A fast and high quality multilevel scheme for partitioning irregular graphs, SIAM Journal on Scientific Computing 20(1): 359–392.
• [25] Liu, J. (1990). The role of elimination trees in sparse factorization, SIAM Journal of Matrix Analysis Applications 11(1): 134–172.
• [26] Niemi, A., Babuška, I., Pitkaranta, J. and Demkowicz, L. (2012). Finite element analysis of the Girkmann problem using the modern hp-version and the classical h-version, Procedia Computer Science 28: 123–134.
• [27] Paszyński, M. (2016). Fast Solvers for Mesh Based Computations, Taylor & Francis/CRC Press, Boca Raton, FL.
• [28] Patro, S.K., Selvam, P.R. and Bosch, H. (2013). Adaptive h-finite element modeling of wind flow around bridges, Engineering Structures 48: 569–577.
• [29] Schaefer, R., Łoś, M., Sieniek, M., Demkowicz, L. And Paszyński, M. (2015). Quasi-linear computational cost adaptive solvers for three dimensional modeling of heating of a human head induced by cell phone, Journal of Computational Science 11: 163–174.
• [30] Strug, B., Paszyńska, A., Paszyński, M. and Grabska, E. (2013). Using a graph grammar system in the finite element method, International Journal of Applied Mathematics and Computer Science 23(4): 839–853, DOI: 10.2478/amcs-2013-0063.
• [31] Zienkiewicz, O.C., Taylor, R. and Z., Z.J. (2013). The Finite Element Method: Its Basis and Fundamentals, Elsevier, Amsterdam.

Uwagi

PL

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