On exploiting sparsity of multiple right-hand sides in sparse direct solvers - Archive ouverte HAL Access content directly
Journal Articles SIAM Journal on Scientific Computing Year : 2019

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

(1, 2) , (3) , (3)
1
2
3

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.
Fichier principal
Vignette du fichier
M115188.pdf (637.7 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01955659 , version 1 (14-12-2018)

Identifiers

Cite

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, 2019, 41 (1), pp.A269-A291. ⟨10.1137/17M1151882⟩. ⟨hal-01955659⟩
114 View
153 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More