Narzędzia użytkownika

Narzędzia witryny


2021:kjopek:start

Zaproszenie na obronę pracy doktorskiej


PRZEWODNICZĄCY I RADA DYSCYPLINY
INFORMATYKI TECHNICZNEJ I TELEKOMUNIKACJI
AKADEMII GÓRNICZO-HUTNICZEJ im. ST. STASZICA W KRAKOWIE
zapraszają na
publiczą dyskusję nad rozprawą doktorską

mgr inż. Konrada Sewiłło-Jopek
Parallel multi-thread multi-frontal solvers using element partition trees
Termin:31 sierpnia 2021 roku o godz. 18:00
Miejsce:spotkanie w formie online, link do spotkania: https://tinyurl.com/4j7arzns
PROMOTOR:Prof. dr hab. Maciej Paszyński, Instytut informatyki, Akademia Górniczo-Hutnicza
PROMOTOR POMOCNICZY: Dr hab. Anna Paszyńska, Wydział Fizyki, Astronomii I Informatyki Stosowanej, Uniwersytet Jagielloński
RECENZENCI:Prof. dr David Pardo, Ikerbasque, the University of the Basque Country UPV/EHU, and the Basque Center for Applied Mathematics (BCAM)
Prof. dr hab. inż. Sergiy Fialko Wydział Informatyki i Telekomunikacji, Politechnika Krakowska
Z rozprawą doktorską i opiniami recenzentów można się zapoznać
w Czytelni Biblioteki Głównej AGH, al. Mickiewicza 30



Parallel multi-thread multi-frontal solvers using element partition trees


mgr inż. Konrad Sewiłło-Jopek


Promotor: prof. dr hab. Maciej Paszyński (AGH) Promotor pomocniczy: dr hab. Anna Paszyńska (UJ) Dyscyplina: Informatyka


Streszczenie

Wejściem dla klasycznych solwerów wielofrontalnych jest macierz rzadka. Solwery te podejmują decyzję odnośnie permutacji macierzy (ordering eliminacji) na podstawie struktury macierzy rzadkiej. Stopień zrównoleglenia zależy także od drzewa eliminacji, stworzonego na podstawie orderingu uzyskanego z macierzy rzadkiej. W przypadku macierzy w obliczeniach inżynierskich, macierze rzadkie uzyskiwane są z siatek obliczeniowych oraz funkcji bazowych rozpiętych na nich. Wiersze i kolumny macierzy są związane z funkcjami bazowymi, a każdy niezerowy wpis w macierzy związany jest z nakładaniem się na siebie nośników funkcji bazowych.

Klasyczne solwery wielofrontalne ignorują dodatkową wiedzę dotyczącą struktury siatki oraz struktury nośników funkcji bazowych rozpiętych na niej. W niniejszej pracy wprowadzona została notacja drzewa partycjonowania elementów, konstruowanego na podstawie siatki obliczeniowej oraz funkcji bazowych. Zaproponowane zostały także algorytmy, które korzystają z drzewa partycjonowania siatki, w szczególności pozwalają na określenie permutacji wierszy i kolumn macierzy wejściowej w taki sposób, aby wynikowy porządek eliminowania generował mniejszą ilość operacji zmiennoprzecinkowych niż orderingi skonstruowane na podstawie globalnej macierzy rzadkiej. Ponadto, proponowane algorytmy pozwalają na deterministyczną lokalizację separatorów C0 dla obliczeń analizy isogeometrycznej, prowadząc do redukcji ilości operacji zmiennoprzecinkowych kosztem obniżenia klasy rozwiązania globalnego. Jako część pracy opracowany został równoległy solwer wielofrontalny, oparty o drzewo podziału elementów, który dla pewnej klasy siatek adaptowalnych okazał się być wydajniejszy od istniejących solwerów ogólnego przeznaczenia. Ostatnim polem zastosowania zaprezentowanych algorytmów jest możliwość użycia solwera bezpośredniego w charakterze preconditionera dla solwerów iteracyjnych, który zwiększa ich zbieżność dla macierzy rzadkich pochodzących z siatek adaptowalnych. W pracy zaprezentowano także zastosowanie takiego solwera do rozwiązania rzeczywistego problemu inżynieryjnego: propagacji fal elektromagnetycznych w formacjach skalnych.

Abstract

The input to the classical multi-frontal solvers is the sparse matrix. They make a decision about the permutation of the matrix (ordering of elimination) based on the structure of the sparse matrix. They parallelization also depends on the elimination tree generated based on the ordering obtained from sparse matrices. In the case of matrices utilized in engineering computations, the sparse matrices are obtained from computational grids, and basis functions span over them. The rows and columns in the matrices are related to the basis functions. The non-zero entries in the matrices are related to the overlap of their supports. The classical multi-frontal solvers ignore the additional knowledge about the computational mesh structure, and the structure and supports of the basis functions span over the mesh. In this dissertation, we introduce the notion of the element partition tree, constructed based on the computational mesh and basis functions, and we propose several algorithms that utilize the concept of the element partition tree. In particular, they allow for (1) determination of the permutation of the rows and columns of the global matrix in such a way that the resulting order of elimination generates a lower number of floating-point operations then orderings constructed based on the structure of the sparse matrix (2) they allow for deterministic localization of the $C^0$ separators for isogeometric analysis computations, resulting in a significant reduction of the computational cost and energy consumption of the multi-frontal solvers (3) they allow for the implementation of the parallel shared-memory multi-frontal solver controlled by the element partition tree, that for a class of adaptive computational grids delivers better performance (4) they allow for the construction of efficient preconditioners for iterative solvers when dealing with adaptive grids. We also present an application of the element partition tree based multi-frontal solvers for the solution of a real engineering problem of propagation of electromagnetic waves into formation layers.


Praca doktorska


Recenzje


Ważniejsze publikacje doktoranta:

  • Hypergraph grammar-based, multi-thread, multi-frontal direct solver scheduled in parallel GALOIS environment / Konrad JOPEK, Maciej PASZYŃSKI, Anna Paszyńska, Muhammad Amber Hassan, Keshav Pingali / Computer Science ; ISSN 1508-2806. — 2019 vol. 20 no. 1, s. 27-55.
  • Applications of a hyper-graph grammar system in adaptive finite-element computations / Piotr Gurgul, Konrad JOPEK, Keshav Pingali, Anna Paszyńska / International Journal of Applied Mathematics and Computer Science ; ISSN 1641-876X. — 2018 vol. 28 no. 3, s. 569–582. — Bibliogr. s. 581–582. — P. Gurgul - afiliacja: Dropbox Inc., San Francisco, USA.
  • Element partition trees for h-refined meshes to optimize direct solver performance. P. 1, Dynamic programming / Hassan AbouEisha, Victor Manuel Calo, Konrad JOPEK, Mikhail Moshkov, Anna Paszyńska, Maciej PASZYŃSKI, Marcin SKOTNICZNY / International Journal of Applied Mathematics and Computer Science ; ISSN 1641-876X. — 2017 vol. 27 no. 2, s. 351–365.
  • Heuristic algorithm to predict the location of C0 separators for efficient isogeometric analysis simulations with direct solvers / A. Paszyńska, K. JOPEK, M. WOŹNIAK, M. PASZYŃSKI / Bulletin of the Polish Academy of Sciences. Technical Sciences ; ISSN 0239-7528. — 2018 vol. 66 no. 6, s. 907–917.
  • Hybrid direct and iterative solver with library of multi-criteria optimal orderings for h adaptive finite element method computations / Hassan AbouEisha, Konrad JOPEK, Bartłomiej Medygrał, Mikhail Moshkov, Szymon Nosek, Anna Paszyńska, Maciej PASZYŃSKI, Keshav Pingali / Procedia Computer Science [Dokument elektroniczny]. - Czasopismo elektroniczne ; ISSN 1877-0509. — 2016 vol. 80, s. 865–874.
  • Quasi-optimal elimination trees for 2D grids with singularities / A. Paszyńska, M. PASZYŃSKI, K. JOPEK, M. WOŹNIAK, D. Goik, P. GURGUL, [et al.] / Scientific Programming ; ISSN 1058-9244. — 2015 Article ID 303024, s. 1–18. —
  • Telescopic hybrid fast solver for 3D elliptic problems with point singularities / Anna Paszyńska, Konrad JOPEK, Krzysztof BANAŚ, Maciej PASZYŃSKI, Piotr GURGUL, Andrew Lenerth, Donald Nguyen, Keshav Pingali, Lisandro Dalcin, Victor Calo / Procedia Computer Science [Dokument elektroniczny]. - Czasopismo elektroniczne ; ISSN 1877-0509. — 2015 vol. 51, s. 2744–2748. — Bibliogr. s. 2748, Abstr.. — ICCS 2015 : International Conference On Computational Science : Computational Science at the Gates of Nature : June 1–3, 2015 in Reykjavík, Iceland.
  • Towards green multi-frontal solver for adaptive finite element method / H. AbbouEisha, M. Moshkov, K. JOPEK, P. Gepner, J. KITOWSKI, M. PASZYŃSKI / Procedia Computer Science [Dokument elektroniczny]. - Czasopismo elektroniczne ; ISSN 1877-0509. — 2015 vol. 51, s. 984–993. — Bibliogr. s. 992–993, Abstr.. — ICCS 2015 : International Conference On Computational Science : Computational Science at the Gates of Nature : June 1–3, 2015 in Reykjavík, Iceland.
  • Using the system of graph grammar for generation of quasi optimal element partition trees in two dimensionsZastosowanie systemu gramatyk grafowych do generacji quasi-optymalnych drzew podziałów siatki w dwóch wymiarach / Anna Paszyńska, Iwona Świderska, Maciej WOŹNIAK, Konrad JOPEK, Maciej PASZYŃSKI, Ewa Grabska, Andrew Lenhart, Donals Nguyen, Keshav Pingali / Computer Methods in Materials Science : quarterly / Akademia Górniczo-Hutnicza ; ISSN 1641-8581. — Tytuł poprz.: Informatyka w Technologii Materiałów. — 2016 vol. 16 no. 3, s. 143–155. — Bibliogr. s. 155, Abstr., Streszcz..

—-

2021/kjopek/start.txt · ostatnio zmienione: 2021/08/23 08:21 przez Konrad Sewiłło-Jopek