Abstract
This paper presents a robust structured multifrontal factorization method for large symmetric positive definite sparse matrices arising from the discretization of partial differential equations (PDEs). For PDEs such as 2D and 3D elliptic equations, the method costs roughly O(n) and O(n 4/3) flops, respectively. The algorithm takes advantage of a low-rank property in the direct factorization of some discretized matrices. We organize the factorization with a supernodal multifrontal method after the nested dissection ordering of the matrix. Dense intermediate matrices in the factorization are approximately factorized into hierarchically semiseparable (HSS) forms, so that a data-sparse Cholesky factor is computed and is guaranteed to exist, regardless of the accuracy of the approximation. We also use an idea of rank relaxation for HSS methods so as to achieve similar performance with flexible structures in broader types of PDE. Due to the structures and the rank relaxation, the performance of the method is relatively insensitive to parameters such as frequencies and sizes of discontinuities. Our method is also much simpler than similar structured multifrontal methods, and is more generally applicable (to PDEs on irregular meshes and to general sparse matrices as a black-box direct solver). The method also has the potential to work as a robust and effective preconditioner even if the low-rank property is insignificant. We demonstrate the efficiency and effectiveness of the method with several important PDEs. Various comparisons with other similar methods are given.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bebendorf, M.: Efficient inversion of the Galerkin matrix of general second-order elliptic operators with nonsmooth coefficients. Math. Comput. 74(251), 1179–1199 (2005)
Bebendorf, M., Hackbusch, W.: Existence of \(\mathcal{H}\)-matrix approximants to the inverse FE-matrix of elliptic operators with l ∞-coefficients. Numer. Math. 95, 1–28 (2003)
Chandrasekaran, S., Dewilde, P., Gu, M., Lyons, W., Pals, T.: A fast solver for HSS representations via sparse matrices. SIAM J. Matrix Anal. Appl. 29, 67–81 (2006)
Chandrasekaran, S., Dewilde, P., Gu, M., Somasunderam, N.: On the numerical rank of the off-diagonal blocks of Schur complements of discretized elliptic PDEs. SIAM J. Matrix Anal. Appl. 31, 2261–2290 (2010)
Chandrasekaran, S., Gu, M., Pals, T.: A fast ULV decomposition solver for hierarchically semiseparable representations. SIAM J. Matrix Anal. Appl. 28, 603–622 (2006)
Chen, L.: iFEM: An innovative finite element methods package in MATLAB. Technical Report (2008). http://math.uci.edu/~chenlong/Papers/iFEMpaper.pdf
Davis, T.A., Hu, Y.: The university of Florida sparse matrix collection. ACM Trans. Math. Softw.
Demmel, J.W., Gilbert, J.R., Li, X.S.: SuperLU Users’ Guide (2003). http://crd.lbl.gov/~xiaoye/SuperLU/
Duff, I.S., Reid, J.K.: The multifrontal solution of indefinite sparse symmetric linear. ACM Trans. Math. Softw. 9, 302–325 (1983)
Eidelman, Y., Gohberg, I.C.: On a new class of structured matrices. Integral Equ. Oper. Theory 34, 293–324 (1999)
Engquist, B., Ying, L.: Sweeping preconditioner for the Helmholtz equation: Hierarchical matrix representation. Commun. Pure Appl. Math. 64, 697–735 (2011)
George, A.: Nested dissection of a regular finite element mesh. SIAM J. Numer. Anal. 10, 345–363 (1973)
Gilbert, J.R., Teng, S.H.: MESHPART, a Matlab mesh partitioning and graph separator toolbox (2002). http://aton.cerfacs.fr/algor/Softs/MESHPART/
Greengard, L., Rokhlin, V.: A fast algorithm for particle simulations. J. Comp. Physiol. 73, 325–348 (1987)
Hackbusch, W.: A sparse matrix arithmetic based on \(\mathcal{H}\)-matrices. Part I: Introduction to \(\mathcal{H}\)-matrices. Computer 62, 89–108 (1999)
Hackbusch, W., Börm, S.: Data-sparse approximation by adaptive \(\mathcal{H}^{2}\)-matrices. Computer 69, 1–35 (2002)
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)
Karypis, G.: METIS: family of multilevel partitioning algorithms (1998). http://glaros.dtc.umn.edu/gkhome/metis/metis/overview
Le Borne, S., Grasedyck, L., Kriemann, R.: Domain-decomposition based \(\mathcal{H}\)-LU preconditioners. Domain Decomposition Methods in Science and Engineering XVI. in O.B. Widlund, D.E. Keyes (Eds) 55, 661–668 (2006)
Liu, J.W.H.: The multifrontal method for sparse matrix solution: Theory and practice. SIAM Rev. 34, 82–109 (1992)
Lyons, W.: Fast algorithms with applications to PDEs. Ph.D. Thesis, UCSB (2005)
Parter, S.: The use of linear graphs in Gauss elimination. SIAM Rev. 3, 119–130 (1961)
Polizzi, E., Sameh, A.H.: A parallel hybrid banded system solver: the SPIKE algorithm. Parallel Comput. 32, 177–194 (2006)
Sambavaram, S.R., Sarin, V., Sameh, A.H., Grama, A.: Multipole-based preconditioners for large sparse linear systems. Parallel Comput. 29, 1261–1273 (2003)
Schmitz, P.G., Ying, L.: A fast direct solver for elliptic problems on general meshes in 2D. J. Comput. Phys. (2011). doi:10.1016/j.jcp.2011.10.013
Schmitz, P.G., Ying, L.: A fast direct solver for elliptic problems on Cartesian meshes in 3D (2011, submitted). http://www.math.utexas.edu/users/lexing/publications/direct3d.pdf
Tewarson, R.P.: On the product form of inverses of sparse matrices. SIAM Rev. 8 (1966)
Vandebril, R., Barel, M.V., Golub, G., Mastronardi, N.: A bibliography on semiseparable matrices. Calcolo 42, 249–270 (2005)
Wang, S., Li, X.S., Xia, J., Situ, Y., de Hoop, V.M.: Efficient scalable algorithms for hierarchically semiseparable matrices. Preprint (2011). http://www.math.purdue.edu/~xiaj/work/parhss.pdf
Xia, J.: Robust structured multifrontal factorization and preconditioning for discretized PDEs. Preprint (2008). http://www.math.purdue.edu/~xiaj/work/mfprec.pdf
Xia, J.: Efficient structured multifrontal factorization for large sparse matrices. Preprint (2010). http://www.math.purdue.edu/~xiaj/work/mfhss.pdf
Xia, J.: On the complexity of some hierarchical structured matrices. SIAM J. Matrix Anal. Appl. (2011, submitted). http://www.math.purdue.edu/~xiaj/work/hsscost.pdf
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)
Xia, J., Chandrasekaran, S., Gu, M., Li, X.S.: Fast algorithms for hierarchically semiseparable matrices. Numer. Linear Algebra Appl. 17, 953–976 (2010)
Xia, J., Gu, M.: Robust approximate Cholesky factorization of rank-structured symmetric positive definite matrices. SIAM J. Matrix Anal. Appl. 31, 2899–2920 (2010)
Acknowledgements
The author thanks Ming Gu, Xiaoye S. Li, and Jie Shen for some useful discussions, and thanks Zhiqiang Cai and Long Chen for providing two test examples. This research was supported in part by NSF grant CHE-0957024.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag London Limited
About this chapter
Cite this chapter
Xia, J. (2012). Robust and Efficient Multifrontal Solver for Large Discretized PDEs. In: Berry, M., et al. High-Performance Scientific Computing. Springer, London. https://doi.org/10.1007/978-1-4471-2437-5_10
Download citation
DOI: https://doi.org/10.1007/978-1-4471-2437-5_10
Publisher Name: Springer, London
Print ISBN: 978-1-4471-2436-8
Online ISBN: 978-1-4471-2437-5
eBook Packages: Computer ScienceComputer Science (R0)