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 metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-01955659
Contributor : Equipe Roma <>
Submitted on : Friday, December 14, 2018 - 3:01:59 PM
Last modification on : Friday, January 10, 2020 - 9:09:25 PM
Long-term archiving on: Friday, March 15, 2019 - 3:36:26 PM

File

M115188.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

151

Files downloads

253