×
Claus, Lisa; Ghysels, Pieter; Liu, Yang; Nhan, Thái Anh; Thirumalaisamy, Ramakrishnan; Bhalla, Amneet Pal Singh; Li, Sherry

Sparse approximate multifrontal factorization with composite compression methods. (English) Zbl 07910039

ACM Trans. Math. Softw. 49, No. 3, Article No. 24, 28 p. (2023).

MSC:

65-XX Numerical analysis

Keywords:

sparse direct solver; multifrontal method; butterfly algorithm; block low-rank compression

Software:

PETSc; zfp; PaStiX; LAPACK
Cite Review PDF
Full Text: DOI

References:

[1] Ambikasaran, Sivaram and Darve, Eric. 2013. An \(\mathcal{O}(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. SIAM J. Sci. Comput.57, 3 (Dec.2013), 477-501. · Zbl 1292.65030
[2] Amestoy, Patrick, Ashcraft, Cleve, Boiteau, Olivier, Buttari, Alfredo, L’Excellent, Jean-Yves, and Weisbecker, Clément. 2015. Improving multifrontal methods by means of block low-rank representations. SIAM J. Sci. Comput.37, 3 (2015), A1451-A1474. · Zbl 1314.05111
[3] Amestoy, Patrick, Buttari, Alfredo, Higham, Nicholas J., L’Excellent, Jean-Yves, Mary, Théo, and Vieuble, Bastien. 2023. Combining sparse approximate factorizations with mixed-precision iterative refinement. ACM Trans. Math. Softw.49, 1 (2023), 1-29. · Zbl 07908566
[4] Amestoy, Patrick R., Buttari, Alfredo, L’Excellent, Jean-Yves, and Mary, Theo. 2019. Performance and scalability of the block low-rank multifrontal factorization on multicore architectures. ACM Trans. Math. Softw.45, 1 (Feb. 2019), Article 2, 26 pages. · Zbl 1471.65025
[5] Anderson, R., Arrighi, W., Elliott, N., Gunney, B., and Hornung, R.. 2013. SAMRAI Concepts and Software Design. Technical Report. LLNL.
[6] Azad, Ariful, Buluç, Aydin, Li, Xiaoye S., Wang, Xinliang, and Langguth, Johannes. 2020. A distributed-memory algorithm for computing a heavy-weight perfect matching on bipartite graphs. SIAM J. Sci. Comput.42, 4 (2020), C143-C168. · Zbl 1451.05189
[7] Balay, S., Abhyankar, S., Adams, M., Brown, J., Brune, P., Buschelman, K., Dalcin, L., Dener, A., Eijkhout, V., Gropp, W., D. Karpeyev, D. Kaushik, M. Knepley, D. May, L. Curfman McInnes, R. Mills, T. Munson, K. Rupp, P. Sanan, B. Smith, S. Zampini, H. Zhang, and H. Zhang. 2018. PETSc Users Manual. Argonne National Laboratory.
[8] Dongarra, Jack J., Duff, Iain S., Sorensen, Danny C., and Vorst, Henk A. van der. 1998. Numerical Linear Algebra for High-Performance Computers. Society for Industrial and Applied Mathematics, Philadelphia, PA. · Zbl 0914.65014
[9] Ghysels, Pieter. 2014. STRUMPACK: STRUctured Matrix PACKage. Retrieved August 7, 2023 from http://portal.nersc.gov/project/sparse/strumpack/
[10] Ghysels, Pieter, Li, Xiaoye Sherry, Gorman, Christopher, and Rouet, François-Henry. 2017. A robust parallel preconditioner for indefinite systems using hierarchical matrices and randomized sampling. In Proceedings of the 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS’17). IEEE, Los Alamitos, CA, 897-906. · Zbl 1436.65057
[11] Karypis, G. and Kumar, V.. 1998. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput.20, 1 (1998), 359-392. · Zbl 0915.68129
[12] Grasedyck, Lars and Hackbusch, Wolfgang. 2003. Construction and arithmetics of h-matrices. Computing70, 4 (2003), 295-334. · Zbl 1030.65033
[13] Griffith, Boyce Eugene. 2005. Simulating the Blood-Muscle-Valve Mechanics of the Heart by an Adaptive and Parallel Version of the Immersed Boundary Method. . New York University.
[14] Griffith, Boyce E., Hornung, Richard D., McQueen, David M., and Peskin, Charles S.. 2007. An adaptive, formally second order accurate version of the immersed boundary method. J. Comput. Phys.223, 1 (2007), 10-49. · Zbl 1163.76041
[15] Hackbusch, Wolfgang. 1999. A sparse matrix arithmetic based on \(\mathcal{H} \) -matrices. Part I: Introduction to \(\mathcal{H} \) -matrices. Computing62, 2 (April1999), 89-108. · Zbl 0927.65063
[16] Hackbusch, Wolfgang, Khoromskij, Boris N., and Kriemann, Ronald. 2004. Hierarchical matrices based on a weak admissibility criterion. Computing73, 3 (2004), 207-243. · Zbl 1063.65035
[17] Hénon, Pascal, Ramet, Pierre, and Roman, Jean. 2002. PaStiX: A high-performance parallel direct solver for sparse symmetric positive definite systems. Parallel Comput.28, 2 (2002), 301-321. · Zbl 0984.68208
[18] Higham, Nicholas J. and Mary, Theo. 2022. Solving block low-rank linear systems by LU factorization is numerically stable. IMA J. Numer. Anal.42, 2 (2022), 951-980. · Zbl 1511.65024
[19] Duff, I. S. and Koster, J.. 1999. The design and use of algorithms for permuting large entries to the diagonal of sparse matrices. SIAM J. Matrix Anal. A.20, 4 (1999), 889901. · Zbl 0947.65048
[20] Duff, I. S. and Reid, J. K.. 1983. The multifrontal solution of indefinite sparse symmetric linear. ACM Trans. Math. Softw.9, 3 (1983), 302-325. · Zbl 0515.65022
[21] Li, Yingzhou and Yang, Haizhao. 2017. Interpolative butterfly factorization. SIAM J. Sci. Comput.39, 2 (2017), A503-A531. · Zbl 1365.65292
[22] Li, Yingzhou, Yang, Haizhao, Martin, Eileen R., Ho, Kenneth L., and Ying, Lexing. 2015. Butterfly factorization. Multiscale Model. Sim.13, 2 (2015), 714-732. · Zbl 1317.44004
[23] Lindstrom, Peter. 2014. Fixed-rate compressed floating-point arrays. IEEE Trans. Vis. Comput. Graph.20 (2014), 2674-2683.
[24] Lindstrom, Peter. 2014. zfp: Compressed Floating-Point and Integer Arrays. Retrieved August 7, 2023 from https://computing.llnl.gov/projects/zfp
[25] Liu, J. W. H.. 1992. The multifrontal method for sparse matrix solution: Theory and practice. SIAM Rev.34 (1992), 82-109. · Zbl 0919.65019
[26] Liu, Yang. 2018. ButterflyPACK. Retrieved August 7, 2023 from https://portal.nersc.gov/project/sparse/butterflypack/
[27] Liu, Yang, Ghysels, Pieter, Claus, Lisa, and Li, Xiaoye Sherry. 2021. Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations. SIAM J. Sci. Comput.43, 5 (2021), S367-S391. · Zbl 1490.65081
[28] Liu, Yang, Guo, Han, and Michielssen, Eric. 2017. An HSS matrix-inspired butterfly-based direct solver for analyzing scattering from two-dimensional objects. IEEE Antennas Wirel. Propag. Lett.16 (2017), 1179-1183.
[29] Liu, Yang, Xing, Xin, Guo, Han, Michielssen, Eric, Ghysels, Pieter, and Li, Xiaoye Sherry. 2021. Butterfly factorization via randomized matrix-vector multiplications. SIAM J. Sci. Comput.43, 2 (2021), A883-A907. · Zbl 1462.65044
[30] MacLachlan, S. and Madden, N.. 2013. Robust solution of singularly perturbed problems using multigrid methods. SIAM J. Sci. Comput.35, 5 (2013), A2225-A2254. SJOCE3 · Zbl 1290.65097
[31] Mary, Théo. 2017. Block Low-Rank Multifrontal Solvers: Complexity, Performance, and Scalability. . l’Université de Toulouse.
[32] Michielssen, Eric and Boag, Amir. 1994. Multilevel evaluation of electromagnetic fields for the rapid solution of scattering problems. Microw. Opt. Technol. Lett.7, 17 (1994), 790-795.
[33] Nangia, Nishant, Griffith, Boyce E., Patankar, Neelesh A., and Bhalla, Amneet Pal Singh. 2019. A robust incompressible Navier-Stokes solver for high density ratio multiphase flows. J. Comput. Phys.390 (2019), 548-594. · Zbl 1452.76157
[34] Nhan, T. A. and Madden, N.. 2015. Cholesky factorisation of linear systems coming from finite difference approximations of singularly perturbed problems. In Boundary and Interior Layers, Computational and Asymptotic Methods—BAIL 2014, Knobloch, Petr (Ed.). Springer International Publishing, Cham, Switzerland, 209-220. · Zbl 1427.65331
[35] Nies, Richard and Hoelzl, Matthias. 2019. Testing performance with and without block low rank compression in MUMPS and the new PaStiX 6.0 for JOREK nonlinear MHD simulations. arXiv e-prints arXiv:1907.13442 (2019).
[36] Operto, Stéphane, Virieux, Jean, Amestoy, Patrick, L’Excellent, Jean-Yves, Giraud, Luc, and Ali, Hafedh Ben Hadj. 2007. 3D finite-difference frequency-domain modeling of visco-acoustic wave propagation using a massively parallel direct solver: A feasibility study. Geophysics72, 5 (2007), SM195-SM211.
[37] Overton, Michael L.. 2001. Numerical Computing with IEEE Floating Point Arithmetic. Society for Industrial and Applied Mathematics, Philadelphia, PA. · Zbl 0981.68057
[38] Pang, Qiyuan, Ho, Kenneth L., and Yang, Haizhao. 2020. Interpolative decomposition butterfly factorization. SIAM J. Sci. Comput.42, 2 (2020), A1097-A1115. · Zbl 1453.65088
[39] Pellegrini, François and Roman, Jean. 1997. Sparse matrix ordering with scotch. In High-Performance Computing and Networking, Hertzberger, Bob and Sloot, Peter (Eds.). Springer, Berlin, Germany, 370-378.
[40] Pichon, Grégoire, Darve, Eric, Faverge, Mathieu, Ramet, Pierre, and Roman, Jean. 2018. Sparse supernodal solver using block low-rank compression: Design, performance and analysis. Int. J. Comput. Sci. Eng.27 (2018), 255-270.
[41] Roos, H.-G., Stynes, M., and Tobiska, L.. 2008. Robust Numerical Methods for Singularly Perturbed Differential Equations (2nd ed.). , Vol. 24. Springer-Verlag, Berlin, Germany. · Zbl 1155.65087
[42] Sayed, Sadeed Bin, Liu, Yang, Gomez, Luis J., and Yucel, Abdulkadir C.. 2022. A butterfly-accelerated volume integral equation solver for broad permittivity and large-scale electromagnetic analysis. IEEE Trans. Antennas Propag.70, 5 (2022), 3549-3559.
[43] Shaeffer, John. 2008. Direct solve of electrically large integral equations for problem sizes to 1 M unknowns. IEEE Trans. Antennas Propag.56, 8 (2008), 2306-2313. · Zbl 1369.78628
[44] Vandebril, Raf, Barel, Marc Van, Golub, Gene, and Mastronardi, Nicola. 2005. A bibliography on semiseparable matrices. CALCOLO42, 3-4 (2005), 249-270. · Zbl 1168.15306
[45] Anderson, E., Z. Bai, C. Bischof, S. Blackford, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, and D. Sorensen. 1999. LAPACK Users’ Guide. Vol. 9. · Zbl 0934.65030
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.