Communication Avoiding Block Low-Rank Parallel Multifrontal Triangular Solve with Many Right-Hand Sides

Patrick Amestoy (1) , Olivier Boiteau (2) , Alfredo Buttari (3) , Matthieu Gerest (2, 4) , Fabienne Jézéquel (4, 5) , Jean-Yves L’excellent (1) , Théo Mary (4)

1 Mumps Technologies [Lyon]
2 EDF R&D - EDF R&D
3 IRIT-APO - Algorithmes Parallèles et Optimisation
4 PEQUAN - Performance et Qualité des Algorithmes Numériques
5 Université Paris-Panthéon-Assas

Block low-rank (BLR) compression can significantly reduce the memory and time costs of parallel sparse direct solvers. In this paper, we investigate the performance of the BLR triangular solve phase, which we observe to be underwhelming when dealing with many right-hand sides (RHS). We explain that this is because the bottleneck of the triangular solve is not in accessing the BLR LU factors, but rather in accessing the RHS, which are uncompressed. Motivated by this finding, we propose several new hybrid variants, which combine the right-looking and left-looking communication patterns to minimize the number of accesses to the RHS. We confirm via a theoretical analysis that these new variants can significantly reduce the total communication volume. We assess the impact of this reduction on the time performance on a range of real-life applications using the MUMPS solver, obtaining up to 20% time reduction.

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

Domains: Computer Science [cs]; Mathematics [math]

Patrick Amestoy, Olivier Boiteau, Alfredo Buttari, Matthieu Gerest, Fabienne Jézéquel, et al.. Communication Avoiding Block Low-Rank Parallel Multifrontal Triangular Solve with Many Right-Hand Sides. SIAM Journal on Matrix Analysis and Applications, 2024, 45 (1), pp.148-166. ⟨10.1137/23M1568600⟩. ⟨hal-04082415⟩