zbMATH — the first resource for mathematics

Multi-core parallel robust structured multifrontal factorization method for large discretized PDEs. (English) Zbl 1330.65050
Summary: In this paper, based on the current mainstream multi-core architecture of parallel computer and the robust structured multifrontal factorization (in brief, RSMF) method, we propose a multi-core parallelization of RSMF (in brief, MRSMF) method. MRSMF method parallelizes the nested dissection ordering, symbolic decomposition and numerical decomposition of RSMF method, which aims to implement these operations on the multi-core parallel machine. The multi-core parallelization of symbolic decomposition and numerical decomposition are based on the binary elimination tree. Numerical experiments show that the MRSMF method is effective.

65F05 Direct numerical methods for linear systems and matrix inversion
15A23 Factorization of matrices
65Y05 Parallel numerical computation
Full Text: DOI
[1] George, J. A., Nested dissection of a regular finite element mesh, SIAM J. Numer. Anal., 10, 345-363, (1973) · Zbl 0259.65087
[2] Hoffman, A. J.; Martin, M. S.; Rose, D. J., Complexity bounds for regular finite difference and finite element grids, SIAM J. Numer. Anal., 10, 364-369, (1973) · Zbl 0261.65026
[3] Bebendorf, M.; Hackbusch, W., Existence of \(H\)-matrix approximants to the inverse \(F E\)-matrix of elliptic operators with \(L^\infty\)-coefficients, Numer. Math., 95, 1-28, (2003) · Zbl 1033.65100
[4] Bebendorf, M., Efficient inversion of Galerkin matrices of general second-order elliptic differential operators with nonsmooth coefficients, Math. Comp., 74, 1179-1199, (2005) · Zbl 1330.65173
[5] Chandrasekaran, S.; Dewilde, P.; Gu, M.; Somasunderam, N., On the numerical rank of the offdiagonal blocks of Schur complements of discretized elliptic pdes, SIAM J. Matrix Anal. Appl., 31, 2261-2290, (2010) · Zbl 1209.65032
[6] Grasedyck, L.; Kriemann, R.; Le Borne, S., Domain-decomposition based \(\mathcal{H} - L U\) preconditioners, (Widlund, O. B.; Keyes, D. E., Domain Decomposition Methods in Science and Engineering XVI, LNCSE, vol. 55, (2006), Springer), 661-668
[7] Xia, J.; Chandrasekaran, S.; Gu, M.; Li, X. S., Superfast multifrontal method for large structured linear systems of equations, SIAM J. Matrix Anal. Appl., 31, 1382-1411, (2009) · Zbl 1195.65031
[8] Börm, S.; Grasedyck, L.; Hackbusch, W., Data-sparse approximation by adaptive \(\mathcal{H}^2\)-matrices, Computing, 69, 1-35, (2002) · Zbl 1012.65023
[9] Eidelman, Y.; Gohberg, I., On a new class of structured matrices, Integral Equations Operator Theory, 34, 293-324, (1999) · Zbl 0934.15002
[10] Hackbusch, W., A sparse matrix arithmetic based on \(H\)-matrices. part I: introduction to \(H\)-matrices, Computing, 62, 89-108, (1999) · Zbl 0927.65063
[11] Vandebril, R.; Van Barel, M.; Golub, G.; Mastronardi, N., A bibliography on semiseparable matrices, Calcolo, 42, 249-270, (2005) · Zbl 1168.15312
[12] Polizzi, E.; Sameh, A., A parallel hybrid banded system solver: the SPIKE algorithm, Parallel Comput., 32, 177-194, (2006)
[13] Sambavarama, S. R.; Sarin, V.; Sameh, A.; Grama, A., Multipole-based preconditioners for large sparse linear systems, Parallel Comput., 29, 1261-1273, (2003)
[14] Wang, S.; Li, X. S.; Xia, J.; Situ, Y.; de Hoop, M. V., Efficient scalable algorithms for solving dense linear systems with hierarchically semiseparable structures, SIAM J. Sci. Comput., 35, 519-544, (2013)
[15] Xia, J., Robust and efficient multifrontal solver for large discretized pdes, (Berry, M. W.; etal., High-Perform. Sci. Comput, (2012), Springer), 199-217
[16] Duff, I. S.; Reid, J. K., The multifrontal solution of indefinite sparse symmetric linear equations, ACM Bans. Math. Softw., 9, 302-325, (1983) · Zbl 0515.65022
[17] Liu, J. W.H., The multifrontal method for sparse matrix solution: theory and practice, SIAM Rev., 34, 82-109, (1992) · Zbl 0919.65019
[18] Xia, J.; Gu, M., Robust approximate Cholesky factorization of rank-structured symmetric positive definite matrices, SIAM J. Matrix Anal. Appl., 31, 2899-2920, (2010) · Zbl 1217.65061
[19] A. Gupta, IBM research report: Parallel sparse direct methods: A short tutorial RC 25076, Computer Science/Mathematics, 2010.
[20] Hadfield, S. M., On the LU factorization of sequences of identically structured sparse matrices within a distributed memory environment, (1994), University of Florida Gainsville, FL, (Ph.D. thesis)
[21] Demmel, J. W.; Gilbert, J. R.; Li, X. S., An asynchronous parallel supernodal algorithm for sparse Gaussian elimination, SIAM J. Matrix Anal. Appl., 20, 4, 915-952, (1999) · Zbl 0939.65036
[22] X.S. Li, J.W. Demmel, J.R. Gilbert, iL. Grigori, M. Shao, I. Yamazaki, SuperLU Users’ Guide, Lawrence Berkeley National Laboratory, 1999. http://crd.lbl.gov/ xiaoye/SuperLU/.
[23] Gupta, A.; Karypis, G.; Kumar, V., Highly scalable parallel algorithms for sparse matrix factorization, IEEE Trans. Parallel Distrib. Syst., 8, 5, 502-520, (1997)
[24] A. Gupta, S. Koric, T. George, Sparse matrix factorization on massively parallel computers, in: SC09 Proceedings, 2009.
[25] Amestoy, P. R.; Duff, I. S.; L’Excellent, J. Y., Multifrontal parallel distributed symmetric and unsymmetric solvers, Comput. Methods Appl. Mech. Eng., 184, 501-520, (2000) · Zbl 0956.65017
[26] Amestoy, P. R.; Duff, I. S.; Koster, J.; L’Excellent, J. Y., A fully asynchronous multifrontal solver using distributed dynamic scheduling, SIAM J. Matrix Anal. Appl., 23, 1, 15-41, (2001) · Zbl 0992.65018
[27] Davis, T. A.; Duff, I. S., An unsymmetric-pattern multifrontal method for sparse LU factorization, SIAM J. Matrix Anal. Appl., 18, 1, 140-158, (1997) · Zbl 0884.65021
[28] Davis, T. A.; Duff, I. S., A combined unifrontal/multifrontal method for unsymmetric sparse matrices, ACM Trans. Math. Softw., 25, 1, 1-19, (1999) · Zbl 0962.65027
[29] Lukarski, D., Parallel sparse linear algebra for multi-core and many-core platforms, (2012), (Ph.D. thesis)
[33] Parter, S. V., The use of linear graphs in Gaussian elimination, SIAM Rev., 3, 119-130, (1961) · Zbl 0102.11302
[34] Tewarson, R. P., On the product form of inverses of sparse matrices and graph theory, SIAM Rev., 9, 91-99, (1967) · Zbl 0168.13302
[35] Schmitz, P.; Ying, L., A fast direct solver for elliptic problems on general meshes in 2D, J. Comput. Phys., 231, 4, 1314-1338, (2012) · Zbl 1408.65022
[36] Grigori, L.; Demmel, J. W.; Li, X. S., Parallel symbolic factorization for sparse LU with static pivoting, SIAM J. Sci. Comput., 29, 3, 1289-1314, (2005) · Zbl 1141.65354
[37] B. Nerma, Sequential and parallel algorithms for cholesky factorization of sparse matrices, Mathematical Applications in Science and Mechanics, Sarajevo School of Science and Technology, ISBN:978-960-474-305-6.
[38] Load Balance and Parallel Performance, By Intel ISN, 8 April 2010.
[39] METIS, Family of multilevel partitioning algorithms. http://glaros.dtc.umn.edu/gkhome/views/metis.
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.