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 the one 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. Given a factorization A = LU of a sparse matrix A and the system AX = B (or LY = B when focusing on the forward elimination), the sparsity of B can be exploited in two ways. First, vertical sparsity is exploited by pruning unnecessary nodes from the elimination tree, which represents the dependencies between computations in a direct method. Second, we explain how horizontal sparsity can be exploited by working on a subset of RHS columns at each node of the tree. A combinatorial problem must then be solved in order to permute the columns of B and minimize the number of operations. We propose a new algorithm to build such a permutation, based on the tree and on the sparsity structure of B. We then propose an original approach to split the columns of B into a minimal number of blocks (to preserve flexibility in the implementation or maintain high arithmetic intensity, for example), while reducing the number of operations down to a given threshold. Both algorithms are motivated by geometric intuitions and designed using an algebraic approach, and they can be applied to general systems of linear equations. 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.
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 : Friday, June 14, 2019 - 6:31:17 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

460

Files downloads

577