Bisection weighted by element size ordering algorithm for multi-frontal solver executed over 3D h refined grids

• Autorzy: Skotniczny M. , Paszyński M , Paszyńska A.

Warianty tytułu

Algorytm bisekcji ważonych rozmiarem elementów do generacji porządku kierującego wykonaniem solwerów wielofrontalnych działających na trójwymiarowych h adaptowanych siatkach obliczeniowych

• Języki publikacji: EN

Abstrakty

EN

In this paper we present an algorithm for generation of ordering over 3D grids h refined towards singularities. The ordering controls the execution of multi-frontal direct solver algorithm on systems of linear equations generated by 3D h adaptive finite element method. The proposed ordering algorithm outperforms other state-of-the-art orderings available through MUMPS interface, namely nested-dissections, AMD and PORD. Our algorithm uses additional knowledge about the structure of the computational mesh, not available to alternative ordering algorithms.

PL

W artykule prezentujemy algorytm generacji porządku eliminacji kierujący wykonaniem solwera wielo-frontalncgo dla trójwymiarowych siatek li adaptowanych do osobliwości punktowych, krawędziowych i ścianowych. Wygenerowany porządek generuje permutacje macierzy układu równań liniowych uzyskanych podczas obliczeń trójwymiarową metodą elementów skończonych. Proponowany algorytm dostarcza porządku eliminacji który pozwala wykonywać faktoryzację z mniejszą liczbą operacji zmienno-przecinkowych niż klasyczne algorytmy generacji porządku dostępne za pośrednictwem solwera MUMPS, takie jak nested-disseetions, AMD oraz PORD. Nasz algorytm wykorzystuje dodatkową wiedzę o strukturze siatki obliczeniowej, nie dostępną dla alternatywnych algorytmów generacji porządku.

Słowa kluczowe

EN

multi-frontal direct solver; hp adaptivity; Finite Element Method; ordering algorithms; element partition tree

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Methods in Materials Science
• Rocznik: 2016
• Tom: Vol. 16, No. 1
• Strony: 54--61
• Opis fizyczny: Bibliogr. 18 poz., rys.

Twórcy

autor

Skotniczny M.

• Department of Computer Science AGH University of Science and Technology, Al. Mickiewicza 30, 30-059 Cracow, Poland

autor

Paszyński M

• Department of Computer Science AGH University of Science and Technology, Al. Mickiewicza 30, 30-059 Cracow, Poland

autor

Paszyńska A.

• Faculty of Physics, Astronomy and Applied Computer Science, Jagiellonian University, ul. St. Łojasiewicza 11, 30-348 Krakow, Poland

Bibliografia

• Abou Eisha, H., Calo, V. M., Jopek, K., Moshkov, M., Paszyńska, A., Paszynski, M., Skotniczny, M., 2016, Element Partition Trees for Two- and Three-Dimensional h-Refined Meshes and Their Use to Optimize Direct Solver Performance, submitted to Journal of Computational Science.
• Amestoy, P. R., Davis, T. A., Du, I. S., 1996, An Approximate Minimum Degree Ordering Algorithm, SIA M Journal of Matrix Analysis & Application, 17(4), 886-905.
• Amestoy, P. R., Duff, I. S., Koster J., L'Excellent, J.-Y., 2001, A fully asynchronous multifrontal solver using distributed dynamic scheduling, SIAM Journal of Matrix Analysis and Applications, 23(l), 15-41.
• Amestoy, P. R. , Guermouche, A., L'Excellent, J.-Y., Pralet, S., 2006, Hybrid scheduling for the parallel solution of linear systems, Parallel Computing, 32(2), 136-156.
• Cottrel, J. A., Bazilevs, Y., Hughes, T.J.R., 2009. Isogeometric Analysis: Toward Integration of CAD and F EA, Dover.
• Bazilevs, Y., Calo, V.M., Cottrell, J.A., Evans, J.A., Lipton, S., Scott, M.A., Sederberg, T.W., 2010. Isogeometric analysis using T-splines, Computer Methods in Applied Mechanics and Engineering, (199) 229-263.
• Demkowicz, L., Bajer, A., Rachowicz, W., Gerdcs, K., 1999. ICES Report 99-29, 3D hp-adaptive finite element package (3Dhp90).
• Demkowicz, L., Kurtz, J., Pardo, D., Paszynski, M., Raehowicz, W., Zdunek, A., 2007. Computing with hp-Finite Elements. Vol. H. Frontiers Three Dimensional Elliptic and Maxwell Problems with Applications, Chapmann & Hall/Crc Applied Mathematics & Nonlinear Science.
• Demkowicz, L, Walsh, T., Gerdes, K., Bajer, A., 1998. ICES Report 98-14, 2D hp-adaptive ñnite element package (2Dhp90).
• George, A., Liu, J .W.-H., 1978, An automatic nested dissection algorithm for irregular finite element problems, SIAM Journal of Numerical Analysis 15, 1053-1069.
• Heggernes, P., Eisenstat, S.C., Kumfert, G., Pothen, A., 2001, The Computational Complexity of the Minimum Degree Algorithm, [CASE Report, No. 2001-42.
• Kaiypis, G., Kumar, V., 1998, A fast and high quality multilevel scheme for partitioning irregular graphs, SIAM Journal of Scientijfic Computing, 20(1), 359-392.
• MUMPS, MUlti-frontal Massively Parallel Sparse direct solver MUMPS, available online at: http://mumps.enseeiht.fr/ accessed: 8.07.2016.
• Paszynska A., Paszyúskí M., Jopek K., Woániak M., Goik D., Gurgul P., AbouEisha H., Moshkov M., Calo V. M., Lenharth V. M., Nguyen D., Pingali K., 2015, Quasi- Optimal Elimination Trees for 2D Grids with Singulanties, Scientific Programming, Article ID 30302411-18.
• Paszynski, M., 2016, Fast Solvers for Mesh Based Computations, Taylor and Francis, CRC Press.
• Paszynski, M., Pardo, D., Calo, V. M., 2015, Direct Solver Performance on h-Adaptive Grids, Computers & Mathematics with Applications, 70(3), 282-295.
• Schaefer, R., Los, M., Sieniek, M., Demkowicz, L., Paszynski, M., 2015, Quasi-linear computational cost adaptive solvers for three dimensional modeling of heating of a human head induced by cell phone, Journal of Computational Science, (1 1), 163-174.
• Schulze, J., 2001, Towards a tighter coupling of bottom-up and top-down sparse matrix ordering methods, BIT, 4l(4), 800.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).