On exploiting sparsity of multiple right-hand sides in sparse direct solvers - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Article Dans Une Revue SIAM Journal on Scientific Computing Année : 2019

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

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

Citer

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⟩
131 Consultations
183 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More