Skip to Main content Skip to Navigation
Journal articles

On exploiting sparsity of multiple right-hand sides in sparse direct solvers

Abstract : The cost of the solution phase in sparse direct methods is sometimes critical. It can be larger than that of the factorization in applications where systems of linear equations with thousands of right-hand sides (RHS) must be solved. In this paper, we focus on the case of multiple sparse RHS with different nonzero structures in each column. In this setting, vertical sparsity reduces the number of operations by avoiding computations on rows that are entirely zero, and horizontal sparsity goes further by performing each elementary solve operation only on a subset of the RHS columns. To maximize the exploitation of horizontal sparsity, we propose a new algorithm to build a permutation of the RHS columns. We then propose an original approach to split the RHS columns into a minimal number of blocks, while reducing the number of operations down to a given threshold. Both algorithms are motivated by geometric intuitions and designed using an algebraic approach, so that they can be applied to general systems. We demonstrate the effectiveness of our algorithms on systems coming from real applications and compare them to other standard approaches. Finally, we give some perspectives and possible applications for this work.
Document type :
Journal articles
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Equipe Roma Connect in order to contact the contributor
Submitted on : Friday, December 14, 2018 - 3:01:59 PM
Last modification on : Wednesday, November 3, 2021 - 9:00:59 AM
Long-term archiving on: : Friday, March 15, 2019 - 3:36:26 PM


Files produced by the author(s)



Patrick Amestoy, Jean-Yves l'Excellent, Gilles Moreau. On exploiting sparsity of multiple right-hand sides in sparse direct solvers. SIAM Journal on Scientific Computing, Society for Industrial and Applied Mathematics, 2019, 41 (1), pp.A269-A291. ⟨10.1137/17M1151882⟩. ⟨hal-01955659⟩



Les métriques sont temporairement indisponibles