Top

Published in:

2018 | OriginalPaper | Chapter

Bisections-Weighted-by-Element-Size-and-Order Algorithm to Optimize Direct Solver Performance on 3D hp-adaptive Grids

Authors : H. AbouEisha, V. M. Calo, K. Jopek, M. Moshkov, A. Paszyńska, M. Paszyński

Published in: Computational Science – ICCS 2018

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The hp-adaptive Finite Element Method (hp-FEM) generates a sequence of adaptive grids with different polynomial orders of approximation and element sizes. The hp-FEM delivers exponential convergence of the numerical error with respect to the mesh size. In this paper, we propose a heuristic algorithm to construct element partition trees. The trees can be transformed directly into the orderings, which control the execution of the multi-frontal direct solvers during the hp refined finite element method. In particular, the orderings determine the number of floating point operations performed by the solver. Thus, the quality of the orderings obtained from the element partition trees is important for good performance of the solver. Our heuristic algorithm has been implemented in 3D and tested on a sequence of hp-refined meshes. We compare the quality of the orderings found by the heuristic algorithm to those generated by alternative state-of-the-art algorithms. We show 50% reduction in flops number and execution time.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Prediction of Blasting Vibration Intensity by Improved PSO-SVR on Apache Spark Cluster

next chapter Establishing EDI for a Clinical Trial of a Treatment for Chikungunya

In [25] the name elimination tree was also used for the element partition tree.

AbouEisha, H., Calo, V.M., Jopek, K., Moshkov, M., Paszyńska, A., Paszyński, M., Skotniczny, M.: Element partition trees for two- and three-dimensional \(h\)-refined meshes and their use to optimize direct solver performance. Dyn. Program. Int. J. Appl. Math. Comput. Sci. (2017, accepted)

Amestoy, P.R., Duff, I.S.: Multifrontal parallel distributed symmetric and unsymmetric solvers. Comput. Methods Appl. Mech. Eng. 184, 501–520 (2000). https://doi.org/10.1016/S0045-7825(99)00242-XCrossRefMATH

Amestoy, P.R., Duff, I.S., Koster, J., L’Excellent, J.-Y.: A fully asynchronous multifrontal solver using distributed dynamic scheduling. SIAM J. Matrix Anal. Appl. 1(23), 15–41 (2001). https://doi.org/10.1137/S0895479899358194MathSciNetCrossRefMATH

Amestoy, P.R., Guermouche, A., L’Excellent, J.-Y., Pralet, S.: Hybrid scheduling for the parallel solution of linear systems. Comput. Methods Appl. Mech. Eng. 2(32), 136–156 (2011). https://doi.org/10.1016/j.parco.2005.07.004CrossRef

Amestoy, P.R., Davis, T.A., Du, I.S.: An approximate minimum degree ordering algorithm. SIAM J. Matrix Anal. Appl. 17(4), 886–905 (1996). https://doi.org/10.1137/S0895479894278952MathSciNetCrossRefMATH

Babuśka, I., Rheinboldt, W.C.: Error estimates for adaptive finite element computations. SIAM J. Num. Anal. 15, 736–754 (1978). https://doi.org/10.1137/0715049MathSciNetCrossRefMATH

Babuska, I., Guo, B.Q.: The \(h\), \(p\) and \(hp\) version of the finite element method: basis theory and applications. Adv. Eng. Softw. 15(3–4), 159–174 (1992). https://doi.org/10.1016/0965-9978(92)90097-YCrossRefMATH

Becker, R., Kapp, J., Rannacher, R.: Adaptive finite element methods for optimal control of partial differential equations: basic concept. SIAM J. Control Optim. 39, 113–132 (2000). https://doi.org/10.1137/S0363012999351097MathSciNetCrossRefMATH

Demkowicz, L., Kurtz, J., Pardo, D., Paszyński, M., Rachowicz, W., Zdunek, A.: Computing with \(hp\) Adaptive Finite Element Method. Part II. Frontiers: Three Dimensional Elliptic and Maxwell Problems with Applications. Chapmann & Hall, CRC Press, Boca Raton, London, New York (2007)

10.

Demkowicz, L., Pardo, D., Rachowicz, W.: Fully automatic \(hp\)-adaptivity in three-dimensions. Comput. Methods Appl. Mech. Eng. 196(37–40), 4816–4842 (2006). https://doi.org/10.1023/A:1015192312705MathSciNetCrossRefMATH

11.

Duff, I.S., Erisman, A.M., Reid, J.K.: Direct Methods for Sparse Matrices. Oxford University Press Inc., New York (1986)MATH

12.

Duff, I.S., Reid, J.K.: The multifrontal solution of indefinite sparse symmetric linear. ACM Trans. Math. Softw. 9(3), 302–325 (1983). https://doi.org/10.1145/356044.356047MathSciNetCrossRefMATH

13.

Duff, I.S., Reid, K.: The multifrontal solution of unsymmetric sets of linear systems. SIAM J. Sci. Comput. 5, 633–641 (1984). https://doi.org/10.1137/0905045CrossRefMATH

14.

Fiałko, S.: A block sparse shared-memory multifrontal finite element solver for problems of structural mechanics. Comput. Assist. Mech. Eng. Sci. 16, 117–131 (2009)

15.

Fiałko, S.: The block subtracture multifrontal method for solution of large finite element equation sets. Tech. Trans. 1-NP 8, 175–188 (2009)

16.

Fiałko, S.: PARFES: a method for solving finite element linear equations on multi-core computers. Adv. Eng. Softw. 40(12), 1256–1265 (2010). https://doi.org/10.1016/j.advengsoft.2010.09.002CrossRefMATH

17.

George, A.: An automatic nested dissection algorithm for irregular finite element problems. SIAM J. Num. Anal. 15, 1053–1069 (1978). https://doi.org/10.1137/0715069MathSciNetCrossRefMATH

18.

Gilbert, J.R., Tarjan, R.E.: The analysis of a nested dissection algorithm. Numer. Math. 50(4), 377–404 (1986/87). https://doi.org/10.1007/BF01396660

19.

Hughes, T.J.R.: The Finite Element Method. Linear Statics and Dynamics Finite Element Analysis. Prentice-Hall, Englewood Cliffs (1987)

20.

Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20(1), 359–392 (1998). https://doi.org/10.1137/S1064827595287997MathSciNetCrossRefMATH

21.

Melenk, J.M.: \(hp\)-Finite Element Methods for Singular Perturbations. Springer, Heidelberg (2002). https://doi.org/10.1007/b84212CrossRefMATH

22.

Niemi, A., Babuśka, I., Pitkaranta, J., Demkowicz, L.: Finite element analysis of the Girkmann problem using the modern \(hp\)-version and the classical \(h\)-version. Eng. Comput. 28, 123–134 (2012). https://doi.org/10.1007/s00366-011-0223-0CrossRef

23.

Paszyńska, A.: Volume and neighbors algorithm for finding elimination trees for three dimensional \(h\)-adaptive grids. Comput. Math. Appl. 68(10), 1467–1478 (2014). https://doi.org/10.1016/j.camwa.2014.09.012MathSciNetCrossRef

24.

Paszyńska, A., Paszyński, M., Jopek, K., Woźniak, M., Goik, D., Gurgul, P., AbouEisha, H., Moshkov, M., Calo, V.M., Lenharth, A., Nguyen, D., Pingali, K.: Quasi-optimal elimination trees for 2D grids with singularities. Sci. Program. 2015, 1–18, Article ID 303024 (2015). https://doi.org/10.1155/2015/303024CrossRef

25.

Paszyński, M.: Fast Solvers for Mesh-Based Computations. Taylor and Francis/CRC Press, Boca Raton, London, New York (2016)MATH

26.

Schwab, C.: \(p\) and \(hp\) Finite Element Methods: Theory and Applications in Solid and Fluid Mechanics. Clarendon Press, Oxford (1998)MATH

27.

Solin, P., Segeth, K., Dolezel, I.: Higher-Order Finite Element Methods. Chapman & Hall/CRC Press, Boca Raton, London, New York (2003)

28.

Szymczak, A., Paszyńska, A., Paszyński, M., Pardo, D.: Preventing deadlock during anisotropic 2D mesh adaptation in hp-adaptive FEM. J. Comput. Sci. 4(3), 170–179 (2013). https://doi.org/10.1016/j.jocs.2011.09.001CrossRef

29.

Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM J. Algebraic Discret. Methods 2, 77–79 (1981). https://doi.org/10.1137/0602010MathSciNetCrossRefMATH

Title: Bisections-Weighted-by-Element-Size-and-Order Algorithm to Optimize Direct Solver Performance on 3D hp-adaptive Grids
Authors: H. AbouEisha
V. M. Calo
K. Jopek
M. Moshkov
A. Paszyńska
M. Paszyński
Publisher: Springer International Publishing
Book: Computational Science – ICCS 2018
Print ISBN: 978-3-319-93700-7

Electronic ISBN: 978-3-319-93701-4

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-93701-4_60

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner