×
Amestoy, Patrick; Boiteau, Olivier; Buttari, Alfredo; Gerest, Matthieu; Jézéquel, Fabienne; L’Excellent, Jean-Yves; Mary, Theo

Communication avoiding block low-rank parallel multifrontal triangular solve with many right-hand sides. (English) Zbl 1535.65052

SIAM J. Matrix Anal. Appl. 45, No. 1, 148-166 (2024).
This paper deals with large sparse linear equations \(AX = B\) for many sparse right hand sides in \(B\). This problem is approached from the triangular decomposition left side by using block low-rank LU factors of the augmented matrix \(A|B\). The proposed algorithm minimizes the access number of the right hand side data in \(B\) with respect to various data or hybridization error categories. A theory is derived and proved for this method’s effect on its smaller memory communication volume in several proposed variants. The theoretical gain of around 20% in speed and communication volume reduction betters standard sparse solvers in various experiments that are performed with tainted image and video data. This data is then reconstructed near accurately and speedily and shows the quality and speed improvements for several such problems in practice.
Reviewer: Frank Uhlig (Auburn)

MSC:

65F50 Computational methods for sparse matrices
65F05 Direct numerical methods for linear systems and matrix inversion
65F55 Numerical methods for low-rank matrix approximation; matrix compression
65Y05 Parallel numerical computation

Keywords:

numerical linear algebra; block low-rank matrices; data sparse matrices; LU factorization; triangular solve; linear systems; low-rank approximations; communication avoiding algorithms

Software:

MUMPS; STRUMPACK
Cite Review PDF
Full Text: DOI

References:

[1] Amestoy, P., Ashcraft, C., Boiteau, O., Buttari, A., L’Excellent, J.-Y., and Weisbecker, C., Improving multifrontal methods by means of block low-rank representations, SIAM J. Sci. Comput., 37 (2015), pp. A1451-A1474, doi:10.1137/120903476. · Zbl 1314.05111
[2] Amestoy, P., Boiteau, O., Buttari, A., Gerest, M., Jezequel, F., L’Excellent, J.-Y., and Mary, T., Mixed precision low-rank approximations and their application to block low-rank LU factorization, IMA J. Numer. Anal., (2022), pp. 1-30, doi:10.1093/imanum/drac037. · Zbl 1525.65038
[3] Amestoy, P., Buttari, A., Higham, N. J., L’Excellent, J.-Y., Mary, T., and Vieublé, B., Combining sparse approximate factorizations with mixed-precision iterative refinement, ACM Trans. Math. Software, 49 (2023), pp. 4:1-4:29, doi:10.1145/3582493. · Zbl 07908566
[4] Amestoy, P. R., Brossier, R., Buttari, A., L’Excellent, J.-Y., Mary, T., Métivier, L., Miniussi, A., and Operto, S., Fast 3D frequency-domain full waveform inversion with a parallel Block Low-Rank multifrontal direct solver: Application to OBC data from the North Sea, Geophysics, 81 (2016), pp. R363-R383, doi:10.1190/geo2016-0052.1.
[5] Amestoy, P. R., Buttari, A., L’Excellent, J.-Y., and Mary, T., On the complexity of the block low-rank multifrontal factorization, SIAM J. Sci. Comput., 39 (2017), pp. A1710-A1740, doi:10.1137/16M1077192. · Zbl 1372.65089
[6] Amestoy, P. R., Buttari, A., L’Excellent, J.-Y., and Mary, T., Performance and scalability of the block low-rank multifrontal factorization on multicore architectures, ACM Trans. Math. Software, 45 (2019), pp. 2:1-2:26, doi:10.1145/3242094. · Zbl 1471.65025
[7] Amestoy, P. R., Duff, I. S., L’Excellent, and J. Koster, J.-Y., A fully asynchronous multifrontal solver using distributed dynamic scheduling, SIAM J. Matrix Anal. Appl., 23 (2001), pp. 15-41. · Zbl 0992.65018
[8] Duff, I. S. and Reid, J. K., The multifrontal solution of indefinite sparse symmetric linear systems, ACM Trans. Math. Software, 9 (1983), pp. 302-325. · Zbl 0515.65022
[9] Ghysels, P., Li, X. S., Rouet, F.-H., Williams, S., and Napov, A., An efficient multicore implementation of a novel HSS-structured multifrontal solver using randomized sampling, SIAM J. Sci. Comput., 38 (2016), pp. S358-S384, doi:10.1137/15M1010117. · Zbl 1352.65092
[10] Hénon, P., Ramet, P., and Roman, J., PaStiX: A high-performance parallel direct solver for sparse symmetric definite systems, Parallel Comput., 28 (2002), pp. 301-321. · Zbl 0984.68208
[11] Higham, N. J. and Mary, T., A new preconditioner that exploits low-rank approximations to factorization error, SIAM J. Sci. Comput., 41 (2019), pp. A59-A82, doi:10.1137/18M1182802. · Zbl 1408.65013
[12] L’Excellent, J.-Y. and Sid-Lakhdar, M. W., A study of shared-memory parallelism in a multifrontal solver, Parallel Comput., 40 (2014), pp. 34-46.
[13] Mary, T., Block Low-Rank Multifrontal Solvers: Complexity, Performance, and Scalability, Ph.D. thesis, Université de Toulouse, 2017.
[14] Operto, S., Amestoy, P., Aghamiry, H., Beller, S., Buttari, A., Combe, L., Dolean, V., Gerest, M., Guo, G., Jolivet, P., L’Excellent, J.-Y., Mamfoumbi, F., Mary, T., Puglisi, C., Ribodetti, A., and Tournier, P.-H., Is 3D frequency-domain FWI of full-azimuth/long-offset OBN data feasible? The Gorgon data FWI case study, The Leading Edge, 42 (2023), pp. 173-183, doi:10.1190/tle42030173.1.
[15] Pichon, G., On the Use of Low-Rank Arithmetic to Reduce the Complexity of Parallel Sparse Linear Solvers Based on Direct Factorization Techniques, Ph.D. thesis, Université de Bordeaux, 2018, https://hal.inria.fr/tel-01953908/.
[16] Pichon, G., Darve, E., Faverge, M., Ramet, P., and Roman, J., Sparse supernodal solver using block low-rank compression: Design, performance and analysis, J. Comput. Sci., 27 (2018), pp. 255-270, doi:10.1016/j.jocs.2018.06.007.
[17] Rouet, F.-H., Li, X. S., Ghysels, P., and Napov, A., A distributed-memory package for dense hierarchically semi-separable matrix computations using randomization, ACM Trans. Math. Software, 42 (2016), pp. 27:1-27:35, doi:10.1145/2930660. · Zbl 1369.65043
[18] Shantsev, D. V., Jaysaval, P., de la Kethulle de Ryhove, S., Amestoy, P. R., Buttari, A., L’Excellent, J.-Y., and Mary, T., Large-scale 3D EM modelling with a block low-rank multifrontal direct solver, Geophys. J. Int., 209 (2017), pp. 1558-1571, doi:10.1093/gji/ggx106.
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.