Skip to Main content Skip to Navigation

On Exploiting Sparsity of Multiple Right-Hand Sides in Sparse Direct Solvers

Patrick Amestoy 1 Jean-Yves l'Excellent 2 Gilles Moreau 2
1 IRIT-APO - Algorithmes Parallèles et Optimisation
IRIT - Institut de recherche en informatique de Toulouse
2 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : The cost of the solution phase in sparse direct methods is sometimes critical. Itcan be larger than the one of the factorization in applications where systems of linear equationswith thousands of right-hand sides (RHS) must be solved. In this paper, we focus on the caseof multiple sparse RHS with different nonzero structures in each column. Given a factorizationA = LU of a sparse matrix A and the system AX = B (or LY = B when focusing on the forwardelimination), the sparsity of B can be exploited in two ways. First, vertical sparsity is exploited bypruning unnecessary nodes from the elimination tree, which represents the dependencies betweencomputations in a direct method. Second, we explain how horizontal sparsity can be exploited byworking on a subset of RHS columns at each node of the tree. A combinatorial problem must thenbe solved in order to permute the columns of B and minimize the number of operations. We proposea new algorithm to build such a permutation, based on the tree and on the sparsity structure ofB. We then propose an original approach to split the columns of B into a minimal number ofblocks (to preserve flexibility in the implementation or maintain high arithmetic intensity, forexample), while reducing the number of operations down to a given threshold. Both algorithmsare motivated by geometric intuitions and designed using an algebraic approach, and they can beapplied to general systems of linear equations. We demonstrate the effectiveness of our algorithmson systems coming from real applications and compare them to other standard approaches. Finally,we give some perspectives and possible applications for this work.
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download
Contributor : Equipe Roma Connect in order to contact the contributor
Submitted on : Tuesday, December 5, 2017 - 2:25:28 PM
Last modification on : Thursday, January 20, 2022 - 5:28:14 PM


Files produced by the author(s)


  • HAL Id : hal-01649244, version 2


Patrick Amestoy, Jean-Yves l'Excellent, Gilles Moreau. On Exploiting Sparsity of Multiple Right-Hand Sides in Sparse Direct Solvers. [Research Report] RR-9122, ENS de Lyon; INRIA Grenoble - Rhone-Alpes. 2017, pp.1-28. ⟨hal-01649244v2⟩



Les métriques sont temporairement indisponibles