Skip to Main content Skip to Navigation
Reports

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 metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-01649244
Contributor : Equipe Roma <>
Submitted on : Tuesday, December 5, 2017 - 2:25:28 PM
Last modification on : Monday, December 14, 2020 - 3:39:28 PM

File

on_exploiting_sparse_rhs_in_di...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01649244, version 2

Citation

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⟩

Share

Metrics

Record views

648

Files downloads

1331