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

H. AbouEisha; Victor Calo; K. Jopek; M. Moshkov; A. Paszyńska; M. Paszyński

doi:10.1007/978-3-319-93701-4_60

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

H. AbouEisha, Victor Calo, K. Jopek, M. Moshkov, A. Paszyńska, M. Paszyński^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 Scopus citations

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.

Original language	English (US)
Title of host publication	Computational Science – ICCS 2018 - 18th International Conference, Proceedings
Editors	Valeria V. Krzhizhanovskaya, Michael Harold Lees, Peter M. Sloot, Jack Dongarra, Yong Shi, Yingjie Tian, Haohuan Fu
Publisher	Springer Verlag
Pages	760-772
Number of pages	13
ISBN (Print)	9783319937007
DOIs	https://doi.org/10.1007/978-3-319-93701-4_60
State	Published - 2018
Event	18th International Conference on Computational Science, ICCS 2018 - Wuxi, China Duration: Jun 11 2018 → Jun 13 2018

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10861 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	18th International Conference on Computational Science, ICCS 2018
Country/Territory	China
City	Wuxi
Period	06/11/18 → 06/13/18

Keywords

Heuristic algorithms
Multi-frontal direct solvers
Nested-dissections
Ordering
hp adaptive finite element method

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-93701-4_60

Cite this

AbouEisha, H., Calo, V., Jopek, K., Moshkov, M., Paszyńska, A., & Paszyński, M. (2018). Bisections-Weighted-by-Element-Size-and-Order Algorithm to Optimize Direct Solver Performance on 3D hp-adaptive Grids. In V. V. Krzhizhanovskaya, M. H. Lees, P. M. Sloot, J. Dongarra, Y. Shi, Y. Tian, & H. Fu (Eds.), Computational Science – ICCS 2018 - 18th International Conference, Proceedings (pp. 760-772). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10861 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-93701-4_60

AbouEisha, H. ; Calo, Victor ; Jopek, K. et al. / Bisections-Weighted-by-Element-Size-and-Order Algorithm to Optimize Direct Solver Performance on 3D hp-adaptive Grids. Computational Science – ICCS 2018 - 18th International Conference, Proceedings. editor / Valeria V. Krzhizhanovskaya ; Michael Harold Lees ; Peter M. Sloot ; Jack Dongarra ; Yong Shi ; Yingjie Tian ; Haohuan Fu. Springer Verlag, 2018. pp. 760-772 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{fdec4e1ce5744c59a65993b3f14866ca,

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

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.",

keywords = "Heuristic algorithms, Multi-frontal direct solvers, Nested-dissections, Ordering, hp adaptive finite element method",

author = "H. AbouEisha and Victor Calo and K. Jopek and M. Moshkov and A. Paszy{\'n}ska and M. Paszy{\'n}ski",

note = "Funding Information: The work was supported by National Science Centre, Poland grant no. DEC-2015/17/B/ST6/01867. Publisher Copyright: {\textcopyright} Springer International Publishing AG, part of Springer Nature 2018.; 18th International Conference on Computational Science, ICCS 2018 ; Conference date: 11-06-2018 Through 13-06-2018",

year = "2018",

doi = "10.1007/978-3-319-93701-4_60",

language = "English (US)",

isbn = "9783319937007",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "760--772",

editor = "Krzhizhanovskaya, {Valeria V.} and Lees, {Michael Harold} and Sloot, {Peter M.} and Jack Dongarra and Yong Shi and Yingjie Tian and Haohuan Fu",

booktitle = "Computational Science – ICCS 2018 - 18th International Conference, Proceedings",

address = "Germany",

}

AbouEisha, H, Calo, V, Jopek, K, Moshkov, M, Paszyńska, A & Paszyński, M 2018, Bisections-Weighted-by-Element-Size-and-Order Algorithm to Optimize Direct Solver Performance on 3D hp-adaptive Grids. in VV Krzhizhanovskaya, MH Lees, PM Sloot, J Dongarra, Y Shi, Y Tian & H Fu (eds), Computational Science – ICCS 2018 - 18th International Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10861 LNCS, Springer Verlag, pp. 760-772, 18th International Conference on Computational Science, ICCS 2018, Wuxi, China, 06/11/18. https://doi.org/10.1007/978-3-319-93701-4_60

Bisections-Weighted-by-Element-Size-and-Order Algorithm to Optimize Direct Solver Performance on 3D hp-adaptive Grids. / AbouEisha, H.; Calo, Victor; Jopek, K. et al.
Computational Science – ICCS 2018 - 18th International Conference, Proceedings. ed. / Valeria V. Krzhizhanovskaya; Michael Harold Lees; Peter M. Sloot; Jack Dongarra; Yong Shi; Yingjie Tian; Haohuan Fu. Springer Verlag, 2018. p. 760-772 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10861 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

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

AU - AbouEisha, H.

AU - Calo, Victor

AU - Jopek, K.

AU - Moshkov, M.

AU - Paszyńska, A.

AU - Paszyński, M.

N1 - Funding Information: The work was supported by National Science Centre, Poland grant no. DEC-2015/17/B/ST6/01867. Publisher Copyright: © Springer International Publishing AG, part of Springer Nature 2018.

PY - 2018

Y1 - 2018

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

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

KW - Heuristic algorithms

KW - Multi-frontal direct solvers

KW - Nested-dissections

KW - Ordering

KW - hp adaptive finite element method

UR - http://www.scopus.com/inward/record.url?scp=85049105839&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-93701-4_60

DO - 10.1007/978-3-319-93701-4_60

M3 - Conference contribution

AN - SCOPUS:85049105839

SN - 9783319937007

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 760

EP - 772

BT - Computational Science – ICCS 2018 - 18th International Conference, Proceedings

A2 - Krzhizhanovskaya, Valeria V.

A2 - Lees, Michael Harold

A2 - Sloot, Peter M.

A2 - Dongarra, Jack

A2 - Shi, Yong

A2 - Tian, Yingjie

A2 - Fu, Haohuan

PB - Springer Verlag

T2 - 18th International Conference on Computational Science, ICCS 2018

Y2 - 11 June 2018 through 13 June 2018

ER -

AbouEisha H, Calo V, Jopek K, Moshkov M, Paszyńska A, Paszyński M. Bisections-Weighted-by-Element-Size-and-Order Algorithm to Optimize Direct Solver Performance on 3D hp-adaptive Grids. In Krzhizhanovskaya VV, Lees MH, Sloot PM, Dongarra J, Shi Y, Tian Y, Fu H, editors, Computational Science – ICCS 2018 - 18th International Conference, Proceedings. Springer Verlag. 2018. p. 760-772. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-93701-4_60

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

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this