Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [27 references]  Display  Hide  Download
Contributor : Pierre Ramet Connect in order to contact the contributor
Submitted on : Thursday, December 20, 2018 - 12:10:31 PM
Last modification on : Friday, November 18, 2022 - 9:26:47 AM
Long-term archiving on: : Friday, March 22, 2019 - 10:13:50 AM


Files produced by the author(s)


  • HAL Id : hal-01961675, version 1



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⟩



Record views


Files downloads