Doktoraty Wydziału IET

mgr inż. Piotr Gurgul

Promotor: dr hab. Maciej Paszyński, prof. nadzw. AGH Dyscyplina: Informatyka

Liczne, a zarazem ważne i trudne problemy inżynierskie wymagają uzyskania przybliżonego rozwiązania pewnego równania różniczkowego cząstkowego. Zważywszy na fakt, iż rozważane problemy generują często miliony niewiadomych, rozwiązanie takiego równania jest zwykle zadaniem wymagającym znacznej mocy obliczeniowej. W rezultacie, algorytmy o niskiej złożoności obliczeniowej są w tej dziedzinie co najmniej tak potrzebne, jak wydajny sprzęt. Używanie metod zapewniających wykładniczy spadek błędu, takich jak hp-adaptacyjna Metoda Elementów Skończonych pozwala w znacznym stopniu ograniczyć liczbę niewiadomych. Najczęstszym przypadkiem wykorzystania algorytmów adaptacyjnych są problemy zawierające jedną lub więcej osobliwości. Kolejny obszar badań w zakresie Metody Elementów Skończonych obejmuje prace nad ulepszeniem działania solwera rozwiązującego wygenerowany układ równań liniowych. Klasyczne solwery dostępne w środowisku naukowym i komercyjnym posiadają złożoność obliczeniową O(N^3/2) dla problemów 2D oraz O(N²) dla problemów 3D, w przypadku stosowania siatek jednorodnych. N oznacza tu liczbę stopni swobody (niewiadomych). Stosowanie adaptacyjnej metody elementów skończonych pozwala znacznie zredukować czas obliczeń solwerów dokładnych. Zdefiniowanie, w oparciu o formalizm gramatyk grafowych, nowego solwera dla problemów adaptacyjnych, wykorzystującego wiedzę o strukturze siatki i gwarantującego w ten sposób złożoność obliczeniową O(N) zarówno dla dwóch, jak i trzech wymiarów pozwoliłoby na kilkukrotne przyspieszenie obliczeń względem dotychczas stosowanych metod. Wyodrębnienie niepodzielnych zadań pod postacią produkcji byłoby również niezwykle przydatne przy opracowaniu wydajnej wersji równoległej solwera. Obiecujący kierunek dalszych badań naukowych będą zapewne stanowić prace nad wykorzystaniem nowoczesnych architektur komputerowych takich jak procesory graficzne.

– Teza rozprawy:– Jako tezę niniejszej rozprawy doktorskiej autor przedstawia następujące twierdzenie:

Istnieje formalizm oparty o gramatyki hipergrafowe, za którego pomocą można opisać dokładny solwer wielofrontalny dla dwu- i trójwymiarowych problemów obliczeniowych z osobliwościami punktowymi, w formie przekształceń zwanych dalej produkcjami, które w prosty sposób pozwalają ustalić porządek wykonania tychże zadań, który gwarantuje liniowy koszt obliczeniowy w wypadku wykonania sekwencyjnego oraz logarytmiczny czas obliczeniowy w wyniku wykonania równoległego.

Niniejsza praca prezentuje nowy formalizm matematyczny, który za pomocą gramatyk hipergrafowych steruje wykonaniem adaptacyjnej Metody Elementów Skończonych dla siatek z osobliwościami punktowymi o dowolnym poziomie zagęszczenia siatki w stronę osobliwości. Rozprawa pokazuje, w jaki sposób wykorzystać szczególną dla problemów z osobliwościami punktowymi strukturę siatki, celem zmniejszenia złożoności obliczeniowej o cały rząd wielkości. Ponadto, zamodelowanie gramatykami hipergrafowymi solwera wielofrontalnego wspomaga wydajne zrównoleglenie, co skutkuje dodatkowym wzrostem wydajności. Modele hipergrafowe zostały w niniejszej rozprawie stworzone zarówno dla sekwencyjnej, jak i równoległej wersji solwera, w dwu i trzech wymiarach. Również proces generacji siatki został opisany produkcjami grafowymi. Dla obu wariantów rozwiązania zostały oszacowane teoretyczne koszta wykonania oraz zużycie pamięci. Modele teoretyczne zostały zaimplementowane na CPU i GPU, a wydajność implementacji porównana z wiodącym obecnie solwerem MUMPS (MUltifrontal Massively Parallel sparse direct Solver). Pomiary wydajności zostały zebrane dla problemów dwu- i trójwymiarowych, z jedną lub wieloma osobliwościami punktowymi oraz dla kilku różnych stopni aproksymacji wielomianowej. Rezultaty te zostały również porównane z oszacowaniami teoretycznymi.

Ważniejsze publikacje doktoranta:

1. Goik D., Sieniek M., Gurgul P., Paszyński M.: Modeling of the absorption of the electromagnetic wave energy in the human head induced by cell phone. Accepted to the Journal of Applied Mathematics and Physics.
2. Paszyński M., Paszyńska A., Jopek K., Woźniak M., Goik D., Gurgul P., AbouEisha H., Moshkov M., Calo V. M., Lenerth A., Nguyen D., Pingali K.: Hypergraph grammar based ordering algorithms for two dimensional grids with singularities. Accepted to Scientific Programming Journal.
3. Gurgul P.: A Linear Complexity Direct Solver for H-adaptive Grids With Point Singularities. Procedia Computer Science, 29(2014): 1090-1099
4. Paszyński M., Gurgul P., Paszyńska A.: Hypergraph grammar based linear computational cost solver for three dimensional grids with point singularities. Procedia Computer Science, 29(2014): 1078-1089.
5. AbouEisha H., Gurgul P., Paszyńska A., Paszyński M., Kuźnik K., Moshkov M. 2014: An automatic way of finding robust elimination trees for a multi-frontal sparse solver for radical 2D hierarchical meshes. Parallel Processing and Applied Mathematics : 10th international conference, PPAM 2013 : Warsaw, Poland, September 8–11, 2013 : revised selected papers, Pt. 2 / eds. Roman Wyrzykowski, [et al.]. — Berlin ; Heidelberg : Springer-Verlag, cop. 2014. — (Lecture Notes in Computer Science ; ISSN 0302-9743 ; 8385. Theoretical Computer Science and General Issues). — ISBN: 978-3-642-55194-9 ; e-ISBN: 978-3-642-55195-6. — pp. 531–540
6. Gurgul P., Sieniek M., Magiera K., Skotniczny M.: Application of multi-agent paradigm to hp-adaptive projection-based interpolation operator. Journal of Computational Science, 3(4): 164–169.
7. Szymczak A., Paszyńska A., Gurgul P., Paszyński M.: Graph grammar based direct solver for hp-adaptive finite element method with point singularities. Procedia Computer Science, 18(2013): 1594-1603.
8. Sieniek M., Gurgul P., Paszyński M.: Employing adaptive finite elements to model squeezing of a layered material in 3D. IJMMM International Journal of Materials, Mechanics and Manufacturing, 1(2013): 319–323.
9. Paszyńska A., Gurgul P., Sieniek M., Paszyński M.: Linear computational cost graph grammar based direct solver for 3D adaptive finite element method simulations. IJMMM International Journal of Materials, Mechanics and Manufacturing, 1(2013): 225–230.
10. Gurgul P., Sieniek M., Paszyński M., Madej Ł., Collier N.: Two-dimensional hp-adaptive algorithm for continuous approximations of material data using space projection. Computer Science Journal, 14(2012): 97–112.
11. Gurgul P., Sieniek M., Paszyński M., Madej Ł.: Three-dimensional adaptive algorithm for continuous approximations of material data using space projection. Computer Methods in Materials Science: quarterly, 13(2013): 245–250.
12. Gurgul P.: New mobile marketing capabilities of the Android platform. Managerial Economics, 12(2012): 119-129.
13. Gurgul P., Sieniek M., Magiera K., Skotniczny M., Paszyński M.: Agent-oriented image processing with the hp-adaptive projection-based interpolation method. Procedia Computer Science, Elsevier, 4(2011): 1844-1853.
14. Sieniek M., Gurgul P., Kołodziejczyk P., Paszyński M.: Agent-based parallel system for numerical computations. Procedia Computer Science, Elsevier, 1(2010): 1971-1981.
15. Gurgul P., Sieniek M., Paszyński M.: Object-oriented Multiscale HP-Adaptive Finite Element Method. Computer Methods in Materials Science, 9(2009): 289-295.