Dynamic Programming Algorithm for Generation of Optimal Elimination Trees for Multi-frontal Direct Solver Over H-refined Grids

Hassan M. AbouEisha; Mikhail Moshkov; Victor M. Calo; Maciej Paszynski; Damian Goik; Konrad Jopek

doi:10.1016/j.procs.2014.05.085

Dynamic Programming Algorithm for Generation of Optimal Elimination Trees for Multi-frontal Direct Solver Over H-refined Grids

Hassan M. AbouEisha, Mikhail Moshkov, Victor M. Calo, Maciej Paszynski, Damian Goik, Konrad Jopek

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

19 Scopus citations

Abstract

In this paper we present a dynamic programming algorithm for finding optimal elimination trees for computational grids refined towards point or edge singularities. The elimination tree is utilized to guide the multi-frontal direct solver algorithm. Thus, the criterion for the optimization of the elimination tree is the computational cost associated with the multi-frontal solver algorithm executed over such tree. We illustrate the paper with several examples of optimal trees found for grids with point, isotropic edge and anisotropic edge mixed with point singularity. We show the comparison of the execution time of the multi-frontal solver algorithm with results of MUMPS solver with METIS library, implementing the nested dissection algorithm.

Original language	English (US)
Title of host publication	Procedia Computer Science
Publisher	Elsevier BV
Pages	947-959
Number of pages	13
DOIs	https://doi.org/10.1016/j.procs.2014.05.085
State	Published - Jun 6 2014

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01

Access to Document

10.1016/j.procs.2014.05.085

https://repository.kaust.edu.sa/bitstream/10754/550843/1/1-s2.0-S1877050914002622-main.pdf

Cite this

@inproceedings{a0bd6edb1dd94d8a9d828910b5561988,

title = "Dynamic Programming Algorithm for Generation of Optimal Elimination Trees for Multi-frontal Direct Solver Over H-refined Grids",

abstract = "In this paper we present a dynamic programming algorithm for finding optimal elimination trees for computational grids refined towards point or edge singularities. The elimination tree is utilized to guide the multi-frontal direct solver algorithm. Thus, the criterion for the optimization of the elimination tree is the computational cost associated with the multi-frontal solver algorithm executed over such tree. We illustrate the paper with several examples of optimal trees found for grids with point, isotropic edge and anisotropic edge mixed with point singularity. We show the comparison of the execution time of the multi-frontal solver algorithm with results of MUMPS solver with METIS library, implementing the nested dissection algorithm.",

author = "AbouEisha, {Hassan M.} and Mikhail Moshkov and Calo, {Victor M.} and Maciej Paszynski and Damian Goik and Konrad Jopek",

note = "KAUST Repository Item: Exported on 2020-10-01",

year = "2014",

month = jun,

day = "6",

doi = "10.1016/j.procs.2014.05.085",

language = "English (US)",

pages = "947--959",

booktitle = "Procedia Computer Science",

publisher = "Elsevier BV",

}

TY - GEN

T1 - Dynamic Programming Algorithm for Generation of Optimal Elimination Trees for Multi-frontal Direct Solver Over H-refined Grids

AU - AbouEisha, Hassan M.

AU - Moshkov, Mikhail

AU - Calo, Victor M.

AU - Paszynski, Maciej

AU - Goik, Damian

AU - Jopek, Konrad

N1 - KAUST Repository Item: Exported on 2020-10-01

PY - 2014/6/6

Y1 - 2014/6/6

N2 - In this paper we present a dynamic programming algorithm for finding optimal elimination trees for computational grids refined towards point or edge singularities. The elimination tree is utilized to guide the multi-frontal direct solver algorithm. Thus, the criterion for the optimization of the elimination tree is the computational cost associated with the multi-frontal solver algorithm executed over such tree. We illustrate the paper with several examples of optimal trees found for grids with point, isotropic edge and anisotropic edge mixed with point singularity. We show the comparison of the execution time of the multi-frontal solver algorithm with results of MUMPS solver with METIS library, implementing the nested dissection algorithm.

AB - In this paper we present a dynamic programming algorithm for finding optimal elimination trees for computational grids refined towards point or edge singularities. The elimination tree is utilized to guide the multi-frontal direct solver algorithm. Thus, the criterion for the optimization of the elimination tree is the computational cost associated with the multi-frontal solver algorithm executed over such tree. We illustrate the paper with several examples of optimal trees found for grids with point, isotropic edge and anisotropic edge mixed with point singularity. We show the comparison of the execution time of the multi-frontal solver algorithm with results of MUMPS solver with METIS library, implementing the nested dissection algorithm.

UR - http://hdl.handle.net/10754/550843

UR - http://linkinghub.elsevier.com/retrieve/pii/S1877050914002622

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

U2 - 10.1016/j.procs.2014.05.085

DO - 10.1016/j.procs.2014.05.085

M3 - Conference contribution

SP - 947

EP - 959

BT - Procedia Computer Science

PB - Elsevier BV

ER -

Dynamic Programming Algorithm for Generation of Optimal Elimination Trees for Multi-frontal Direct Solver Over H-refined Grids

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this