Bisection weighted by element size ordering algorithm for multi-frontal solver executed over 3D h refined grids
Marcin Skotniczny1, Maciej Paszyński1
, Anna Paszyńska2
1Department of Computer Science AGH University of Science and Technology, Al. Mickiewicza 30, 30-059 Cracow, Poland.
2Faculty of Physics, Astronomy and Applied Computer Science, Jagiellonian University, ul. St. Łojasiewicza 11, 30-348 Krakow, Poland.
DOI:
https://doi.org/10.7494/cmms.2016.1.0560
Abstract:
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. Our algorithm uses additional knowledge about the structure of the computational mesh, not available to alternative ordering algorithms. The proposed ordering algorithm outperforms other state-of-the-art orderings available through MUMPS interface, namely nested-dissections, AMD and PORD.
Cite as:
Skotniczny, M., Paszyński, M., Paszyńska, A. (2016). Bisection weighted by element size ordering algorithm for multi-frontal solver executed over 3D h refined grids. Computer Methods in Materials Science, 16(1), 54 – 61. https://doi.org/10.7494/cmms.2016.1.0560
Article (PDF):
Keywords:
Finite Element Method, Hp adaptivity, Multi-frontal direct solver, Element partition tree, Ordering algorithm
References:
AbouEisha, H., Calo, V. M., Jopek, K., Moshkov, M.,Paszyńska, A., Paszyński, M., Skotniczny, M., 2016, ElementPartition Trees for Two- and Three-Dimensionalh-Refined Meshes and Their Use to Optimize DirectSolver Performance, submitted to Journal of ComputationalScience.
Amestoy, P. R., Davis, T. A., Du, I. S., 1996, An ApproximateMinimum Degree Ordering Algorithm, SIAM Journal ofMatrix Analysis & Application, 17(4), 886-905.
Amestoy, P. R., Duff, I. S., Koster J., L’Excellent, J.-Y., 2001, Afully asynchronous multifrontal solver using distributeddynamic scheduling, SIAM Journal of Matrix Analysisand Applications, 23(1), 15-41.
Amestoy, P. R. , Guermouche, A., L’Excellent, J.-Y., Pralet, S.,2006, Hybrid scheduling for the parallel solution of linearsystems, Parallel Computing, 32(2), 136-156.
Cottrel, J. A., Bazilevs, Y., Hughes, T.J.R., 2009. IsogeometricAnalysis: Toward Integration of CAD and FEA,
Dover. Bazilevs, Y., Calo, V.M., Cottrell, J.A., Evans, J.A., Lipton, S.,Scott, M.A., Sederberg, T.W., 2010. Isogeometric analysisusing T-splines, Computer Methods in Applied Mechanicsand Engineering, (199) 229-263.
Demkowicz, L., Bajer, A., Rachowicz, W., Gerdes, K., 1999.
ICES Report 99-29, 3D hp-adaptive finite element package(3Dhp90).Demkowicz, L., Kurtz, J., Pardo, D., Paszyński, M., Rachowicz,W., Zdunek, A., 2007. Computing with hp-Finite Elements.Vol. II. Frontiers Three Dimensional Elliptic andMaxwell Problems with Applications, Chapmann &Hall/Crc Applied Mathematics & Nonlinear Science.Demkowicz, L, Walsh, T., Gerdes, K., Bajer, A., 1998. ICESReport 98-14, 2D hp-adaptive finite element package(2Dhp90).
George, A., Liu, J.W.-H., 1978, An automatic nested dissectionalgorithm for irregular finite element problems, SIAMJournal of Numerical Analysis 15, 1053-1069.
Heggernes, P., Eisenstat, S.C., Kumfert, G., Pothen, A., 2001,The Computational Complexity of the Minimum DegreeAlgorithm, ICASE Report, No. 2001-42.
Karypis, G., Kumar, V., 1998, A fast and high quality multilevelscheme for partitioning irregular graphs, SIAM Journalof Scientiffic Computing, 20(1), 359-392.
MUMPS, MUlti-frontal Massively Parallel Sparse direct solverMUMPS, available online at: http://mumps.enseeiht.fr/accessed: 8.07.2016.
Paszyńska A., Paszyński 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 Singularities,Scientific Programming, Article ID 303024:1-18.
Paszyński, M., 2016, Fast Solvers for Mesh Based Computations,Taylor and Francis, CRC Press.Paszynski, M., Pardo, D., Calo, V. M., 2015, Direct SolverPerformance on h-Adaptive Grids, Computers & Mathematicswith Applications, 70(3), 282-295.
Schaefer, R., Łoś, M., Sieniek, M., Demkowicz, L., Paszyński,M., 2015, Quasi-linear computational cost adaptivesolvers for three dimensional modeling of heating ofa human head induced by cell phone, Journal of ComputationalScience, (11), 163-174.
Schulze, J., 2001, Towards a tighter coupling of bottom-up andtop-down sparse matrix ordering methods, BIT, 41(4), 800.