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

Hassan M. AbouEisha, Piotr Gurgul, Anna Paszyńska, Maciej R. Paszyński, Krzysztof M. Kuźnik, Mikhail Moshkov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

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.
Original languageEnglish (US)
Title of host publicationParallel Processing and Applied Mathematics
PublisherSpringer Nature
Pages531-540
Number of pages10
ISBN (Print)9783642551949
DOIs
StatePublished - May 8 2014

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'An automatic way of finding robust elimination trees for a multi-frontal sparse solver for radical 2D hierarchical meshes'. Together they form a unique fingerprint.

Cite this