Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Deciding Non-Compressible Blocks in Sparse Direct Solvers using Incomplete Factorization

Esragul Korkmaz 1 Mathieu Faverge 1 Grégoire Pichon 2 Pierre Ramet 1
1 HiePACS - High-End Parallel Algorithms for Challenging Numerical Simulations
LaBRI - Laboratoire Bordelais de Recherche en Informatique, Inria Bordeaux - Sud-Ouest
2 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Low-rank compression techniques are very promising for reducing memory footprintand execution time on a large spectrum of linear solvers. Sparse direct supernodal approaches areone these techniques. However, despite providing a very good scalability and reducing the memoryfootprint, they suffer from an important flops overhead in their unstructured low-rank updates.As a consequence, the execution time is not improved as expected. In this paper, we study asolution to improve low-rank compression techniques in sparse supernodal solvers. The proposedmethod tackles the overprice of the low-rank updates by identifying the blocks that have poorcompression rates. We show that block incomplete LU factorization, thanks to the block fill-inlevels, allows to identify most of these non-compressible blocks at low cost. This identificationenables to postpone the low-rank compression step to trade small extra memory consumption fora better time to solution. The solution is validated within thePaStiXlibrary with a large set ofapplication matrices. It demonstrates sequential and multi-threaded speedup up to 8.5x, for smallmemory overhead of less than 1.49xwith respect to the original version.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Mathieu Faverge <>
Submitted on : Thursday, February 25, 2021 - 10:10:15 PM
Last modification on : Thursday, March 4, 2021 - 3:27:48 AM


Files produced by the author(s)


  • HAL Id : hal-03152932, version 1


Esragul Korkmaz, Mathieu Faverge, Grégoire Pichon, Pierre Ramet. Deciding Non-Compressible Blocks in Sparse Direct Solvers using Incomplete Factorization. 2021. ⟨hal-03152932v1⟩



Record views


Files downloads