×

zbMATH — the first resource for mathematics

A scalable parallel factorization of finite element matrices with distributed Schur complements. (English) Zbl 1413.65415
Summary: We consider the parallel factorization of sparse finite element matrices on distributed memory machines. Our method is based on a nested dissection approach combined with a cyclic re-distribution of the interface Schur complements. We present a detailed definition of the parallel method, and the well-posedness and the complexity of the algorithm are analyzed. A lean and transparent functional interface to existing finite element software is defined, and the performance is demonstrated for several representative examples.

MSC:
65N22 Numerical solution of discretized equations for boundary value problems involving PDEs
65F05 Direct numerical methods for linear systems and matrix inversion
65Y05 Parallel numerical computation
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Toselli, Domain Decomposition Methods - Algorithms and Theory (2005) · Zbl 1069.65138 · doi:10.1007/b137868
[2] Maurer, A parallel block LU decomposition method for distributed finite element matrices, Parallel Computing 37 (12) pp 742– (2011) · Zbl 06094856 · doi:10.1016/j.parco.2011.05.007
[3] Golub, Matrix Computations (1996)
[4] Demmel, Stability of block algorithms with fast level-3 blas, ACM Transactions on Mathematical Software (TOMS) 18 (3) pp 274– (1992) · Zbl 0892.65016 · doi:10.1145/131766.131769
[5] Mattheij, Stability of block lu-decompositions of matrices arising from bvp, SIAM Journal on Algebraic Discrete Methods 5 (3) pp 314– (1984) · Zbl 0559.65014 · doi:10.1137/0605033
[6] Demmel, Stability of block LU factorization, Numerical Linear Algebra with Applications 2 pp 173– (1995) · Zbl 0834.65010 · doi:10.1002/nla.1680020208
[7] Amestoy, A fully asynchronous multifrontal solver using distributed dynamic scheduling, SIAM Journal on Matrix Analysis and Applications 23 (1) pp 15– (2001) · Zbl 0992.65018 · doi:10.1137/S0895479899358194
[8] Schenk, Lecture Notes Computational Sciences, in: Computational Science - ICCS 2002. 2nd International Conference, Amsterdam, the Netherlands, April. 21-24, 2002. Proceedings. Part 2 pp 355– (2002) · doi:10.1007/3-540-46080-2_37
[9] Schenk, PARDISO: A high-performance serial and parallel sparse linear solver in semiconductor device simulation, FGCS. Future Generation Computer Systems 18 (1) pp 69– (2001) · Zbl 1032.68172 · doi:10.1016/S0167-739X(00)00076-5
[10] Schenk, Matching-based preprocessing algorithms to the solution of saddle-point problems in large-scale nonconvex interior-point optimization, Computational Optimization and Applications 36 pp 321– (2007) · Zbl 1146.90055 · doi:10.1007/s10589-006-9003-y
[11] Polizzi, SPIKE: A parallel environment for solving banded linear systems, Computational Fluids 36 (1) pp 113– (2007) · Zbl 1181.76110 · doi:10.1016/j.compfluid.2005.07.005
[12] Henon, Pastix: a high-performance parallel direct solver for sparse symmetric positive definite systems, Parallel Computing 28 (2) pp 301– (2002) · Zbl 0984.68208 · doi:10.1016/S0167-8191(01)00141-7
[13] Balay, Modern Software Tools in Scientific Computing pp 163– (1997) · doi:10.1007/978-1-4612-1986-6_8
[14] Demmel, A supernodal approach to sparse partial pivoting, SIAM Journal Matrix Analysis and Applications 20 (3) pp 720– (1999) · Zbl 0931.65022 · doi:10.1137/S0895479895291765
[15] Davis TA User’s guide for the unsymmetric-pattern multifrontal package (umfpack). Tech. Report TR-95-004 Gainesville, FL 1995
[16] Dackland K Elmroth E Kågström B Loan CV Design and Evaluation of Parallel Block Algorithms: LU Factorization on an IBM 3090 VF/600J Proceedings of the Fifth SIAM Conference on Parallel Processing for Scientific Computing Philadelphia, PA, USA 1992 3 10 · Zbl 0788.65027
[17] Dongarra, Solving Linear Systems on Vector and Shared Memory Computers (1990) · Zbl 0770.65009
[18] Gallivan, Parallel algorithms for dense linear algebra computations, SIAM Review 32 pp 54– (1990) · Zbl 0697.65010 · doi:10.1137/1032002
[19] Bomhof, A parallel linear system solver for circuit simulation problems, Numerical Linear Algebra with Applications 7 (7-8) pp 649– (2000) · Zbl 1051.65028 · doi:10.1002/1099-1506(200010/12)7:7/8<649::AID-NLA217>3.0.CO;2-W
[20] Hackbusch, Hierarchical Matrices: Algorithms and Analysis (2016)
[21] Grasedyck, Parallel black box -LU preconditioning for elliptic boundary value problems, Computing and Visualization in Science 11 (4-6) pp 273– (2008) · doi:10.1007/s00791-008-0098-9
[22] Grasedyck, Domain decomposition based -LU preconditioning, Numerische Mathematik 112 (4) pp 565– (2009) · Zbl 1178.65140 · doi:10.1007/s00211-009-0218-6
[23] Wieners C Distributed point objects. A new concept for parallel finite elements 2005 175 182
[24] Wieners, A geometric data structure for parallel finite elements and the application to multigrid methods with block smoothing, Computing and Visualization in Sciences 13 (4) pp 161– (2010) · Zbl 1216.65164 · doi:10.1007/s00791-010-0135-3
[25] Anderson, LAPACK’S user’s Guide (1992)
[26] Anderson E Bai Z Bischof C Demmel J Dongarra J Croz JD Greenbaum A Hammarling S McKenney A Sorensen D Lapack: A portable linear algebra library for high-performance computers 1990
[27] Maurer D Ein hochskalierbarer paralleler direkter Löser für Finite Elemente Diskretisierungen Ph.D. Thesis 2013
[28] Williams, Performance of dynamic load balancing algorithms for unstructured mesh calculations, Concurrency: Practice and Experience 3 (5) pp 457– (1991) · doi:10.1002/cpe.4330030502
[29] Bastian, A generic grid interface for parallel and adaptive scientific computing. Part I: Abstract framework, Computing 82 (2-3) pp 103– (2008) · Zbl 1151.65089 · doi:10.1007/s00607-008-0003-x
[30] Bastian, A generic grid interface for parallel and adaptive scientific computing. Part II: Implementation and tests in DUNE, Computing 82 (2-3) pp 121– (2008) · Zbl 1151.65088 · doi:10.1007/s00607-008-0004-9
[31] Bangerth, deal.II-a general-purpose object-oriented finite element library, ACM Transactions on Mathematical Software (TOMS) 33 (4) (2007) · Zbl 1365.65248 · doi:10.1145/1268776.1268779
[32] Bastian, UG - a flexible software toolbox for solving partial differential equations, Computing and Visualization in Sciences 1 pp 27– (1997) · Zbl 0970.65129 · doi:10.1007/s007910050003
[33] Elman, Finite Elements and Fast Iterative Solvers with Applications in Incompressible Fluid Dynamics (2005) · Zbl 1083.76001
[34] Boffi, Springer Series in Computational Mathematics, in: Mixed finite element methods and applications (2013) · Zbl 1277.65092 · doi:10.1007/978-3-642-36519-5
[35] Ciarlet, Studies in Mathematics and its Applications, in: Three-Dimensional Elasticity (1988)
[36] Sanders P Schulz C Engineering multilevel graph partitioning algorithms ESA Springer: Berlin 2011 469 480
[37] Hochbruck, Efficient time integration for discontinuous Galerkin approximations of linear wave equations, ZAMM: Journal of Applied Mathematics and Mechanics 95 (3) pp 237– (2015) · Zbl 1322.65095 · doi:10.1002/zamm.201300306
[38] Maurer, High Performance Computing in Science and Engineering ’13 pp 671– (2013)
[39] Maurer, Proceedings of the CiHPC 2010: Competence in High Performance Computing pp 205– (2012)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.