Supernodes ordering to enhance Block Low-Rank compression in sparse direct solvers

Abstract : Solving sparse linear systems appears in many scientific applications, and sparse direct linear solvers are widely used for their robustness. Still, both time and memory complexities limit the use of direct methods to solve larger problems, while the amount of memory available per computational units is decreasing in modern architectures. In order to tackle this problem, low-rank compression techniques have been introduced in direct solvers to compress large dense blocks appearing in the symbolic factorization. In this paper, we consider the Block Low-Rank (BLR) compression format and address the problem of clustering unknowns that come from separators issued from the nested dissection process. We show that methods considering only intra-separators connectivity (i.e., k-way or recursive bisection) as well as methods managing only interaction between separators have limitations. We propose a new strategy that considers interactions between multiple levels of the elimination tree of the nested dissection. This strategy tries to both reduce the number of off-diagonal blocks in the symbolic structure and increase the compression ratio of the large separators. We demonstrate how this new method enhances the BLR strategies in the sparse direct supernodal solver PaStiX.
Complete list of metadatas

https://hal.inria.fr/hal-01961675
Contributor : Pierre Ramet <>
Submitted on : Thursday, December 20, 2018 - 12:10:31 PM
Last modification on : Thursday, February 7, 2019 - 1:59:59 PM
Long-term archiving on : Friday, March 22, 2019 - 10:13:50 AM

File

RR-9238.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01961675, version 1

Citation

Grégoire Pichon, Eric Darve, Mathieu Faverge, Pierre Ramet, Jean Roman. Supernodes ordering to enhance Block Low-Rank compression in sparse direct solvers. [Research Report] RR-9238, Inria Bordeaux Sud-Ouest. 2018, pp.1-31. ⟨hal-01961675⟩

Share

Metrics

Record views

179

Files downloads

52