TY - GEN

T1 - An automatic way of finding robust elimination trees for a multi-frontal sparse solver for radical 2D hierarchical meshes

AU - AbouEisha, Hassan M.

AU - Gurgul, Piotr

AU - Paszyńska, Anna

AU - Paszyński, Maciej R.

AU - Kuźnik, Krzysztof M.

AU - Moshkov, Mikhail

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

PY - 2014/5/8

Y1 - 2014/5/8

N2 - In this paper we present a dynamic programming algorithm for finding optimal elimination trees for the multi-frontal direct solver algorithm executed over two dimensional meshes with point singularities. The elimination tree found by the optimization algorithm results in a linear computational cost of sequential direct solver. Based on the optimal elimination tree found by the optimization algorithm we construct heuristic sequential multi-frontal direct solver algorithm resulting in a linear computational cost as well as heuristic parallel multi-frontal direct solver algorithm resulting in a logarithmic computational cost. The resulting parallel algorithm is implemented on NVIDIA CUDA GPU architecture based on our graph-grammar approach. © 2014 Springer-Verlag.

AB - In this paper we present a dynamic programming algorithm for finding optimal elimination trees for the multi-frontal direct solver algorithm executed over two dimensional meshes with point singularities. The elimination tree found by the optimization algorithm results in a linear computational cost of sequential direct solver. Based on the optimal elimination tree found by the optimization algorithm we construct heuristic sequential multi-frontal direct solver algorithm resulting in a linear computational cost as well as heuristic parallel multi-frontal direct solver algorithm resulting in a logarithmic computational cost. The resulting parallel algorithm is implemented on NVIDIA CUDA GPU architecture based on our graph-grammar approach. © 2014 Springer-Verlag.

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

UR - http://link.springer.com/10.1007/978-3-642-55195-6_50

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

U2 - 10.1007/978-3-642-55195-6_50

DO - 10.1007/978-3-642-55195-6_50

M3 - Conference contribution

SN - 9783642551949

SP - 531

EP - 540

BT - Parallel Processing and Applied Mathematics

PB - Springer Nature

ER -