Hybrid Direct and Iterative Solver with Library of Multi-criteria Optimal Orderings for h Adaptive Finite Element Method Computations

Hassan M. AbouEisha, Konrad Jopek, Bartłomiej Medygrał, Mikhail Moshkov, Szymon Nosek, Anna Paszyńska, Maciej Paszyński, Keshav Pingali

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


In this paper we present a multi-criteria optimization of element partition trees and resulting orderings for multi-frontal solver algorithms executed for two dimensional h adaptive finite element method. In particular, the problem of optimal ordering of elimination of rows in the sparse matrices resulting from adaptive finite element method computations is reduced to the problem of finding of optimal element partition trees. Given a two dimensional h refined mesh, we find all optimal element partition trees by using the dynamic programming approach. An element partition tree defines a prescribed order of elimination of degrees of freedom over the mesh. We utilize three different metrics to estimate the quality of the element partition tree. As the first criterion we consider the number of floating point operations(FLOPs) performed by the multi-frontal solver. As the second criterion we consider the number of memory transfers (MEMOPS) performed by the multi-frontal solver algorithm. As the third criterion we consider memory usage (NONZEROS) of the multi-frontal direct solver. We show the optimization results for FLOPs vs MEMOPS as well as for the execution time estimated as FLOPs+100MEMOPS vs NONZEROS. We obtain Pareto fronts with multiple optimal trees, for each mesh, and for each refinement level. We generate a library of optimal elimination trees for small grids with local singularities. We also propose an algorithm that for a given large mesh with identified local sub-grids, each one with local singularity. We compute Schur complements over the sub-grids using the optimal trees from the library, and we submit the sequence of Schur complements into the iterative solver ILUPCG.
Original languageEnglish (US)
Pages (from-to)865-874
Number of pages10
JournalProcedia Computer Science
StatePublished - Jun 2 2016

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: The work presented in this paper has been supported by National Science Centre, Poland grant no. DEC-2015/17/B/ST6/01867 and by King Abdullah University of Science and Technology (KAUST).


Dive into the research topics of 'Hybrid Direct and Iterative Solver with Library of Multi-criteria Optimal Orderings for h Adaptive Finite Element Method Computations'. Together they form a unique fingerprint.

Cite this