Geodesic
Element partition trees for h-refined meshes to optimize direct solver performance. Part I: Dynamic programming
International Journal of Applied Mathematics and Computer Science, Tome 27 (2017) no. 2, pp. 351-365.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: h-adaptive finite element method, ordering, element partition tree, extensions of dynamic programming, multifrontal direct solvers
Mots-clés : metoda elementów skończonych, porządkowanie danych, programowanie dynamiczne 
@article{IJAMCS_2017_27_2_a9,
     author = {Aboueisha, H. and Calo, V. M. and Jopek, K. and Moshkov, M. and Paszy\'nska, A. and Paszy\'nski, M. and Skotniczny, M.},
     title = {Element partition trees for h-refined meshes to optimize direct solver performance. {Part} {I:} {Dynamic} programming},
     journal = {International Journal of Applied Mathematics and Computer Science},
     pages = {351--365},
     publisher = {mathdoc},
     volume = {27},
     number = {2},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IJAMCS_2017_27_2_a9/}
}
TY  - JOUR
AU  - Aboueisha, H.
AU  - Calo, V. M.
AU  - Jopek, K.
AU  - Moshkov, M.
AU  - Paszyńska, A.
AU  - Paszyński, M.
AU  - Skotniczny, M.
TI  - Element partition trees for h-refined meshes to optimize direct solver performance. Part I: Dynamic programming
JO  - International Journal of Applied Mathematics and Computer Science
PY  - 2017
SP  - 351
EP  - 365
VL  - 27
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IJAMCS_2017_27_2_a9/
LA  - en
ID  - IJAMCS_2017_27_2_a9
ER  - 
%0 Journal Article
%A Aboueisha, H.
%A Calo, V. M.
%A Jopek, K.
%A Moshkov, M.
%A Paszyńska, A.
%A Paszyński, M.
%A Skotniczny, M.
%T Element partition trees for h-refined meshes to optimize direct solver performance. Part I: Dynamic programming
%J International Journal of Applied Mathematics and Computer Science
%D 2017
%P 351-365
%V 27
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IJAMCS_2017_27_2_a9/
%G en
%F IJAMCS_2017_27_2_a9
Aboueisha, H.; Calo, V. M.; Jopek, K.; Moshkov, M.; Paszyńska, A.; Paszyński, M.; Skotniczny, M. Element partition trees for h-refined meshes to optimize direct solver performance. Part I: Dynamic programming. International Journal of Applied Mathematics and Computer Science, Tome 27 (2017) no. 2, pp. 351-365. http://geodesic.mathdoc.fr/item/IJAMCS_2017_27_2_a9/

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