Skip to Main content Skip to Navigation

Trading Performance for Memory in Sparse Direct Solvers using Low-rank Compression

Abstract : Sparse direct solvers using Block Low-Rank compression have been proven efficient to solve problems arising in many real-life applications. Improving those solvers is crucial for being able to 1) solve larger problems and 2) speed up computations. A main characteristic of a sparse direct solver using low-rank compression is when compression is performed. There are two distinct approaches: (1) all blocks are compressed before starting the factorization, which reduces the memory as much as possible, or (2) each block is compressed as late as possible, which usually leads to better speedup. The objective of this paper is to design a composite approach, to speedup computations while staying under a given memory limit. This should allow to solve large problems that cannot be solved with Approach 2 while reducing the execution time compared to Approach 1. We propose a memory-aware strategy where each block can be compressed either at the beginning or as late as possible. We first consider the problem of choosing when to compress each block, under the assumption that all information on blocks is perfectly known, i.e., memory requirement and execution time of a block when compressed or not. We show that this problem is a variant of the NP-complete Knapsack problem, and adapt an existing 2-approximation algorithm for our problem. Unfortunately, the required information on blocks depends on numerical properties and in practice cannot be known in advance. We thus introduce models to estimate those values. Experiments on the PaStiX solver demonstrate that our new approach can achieve an excellent trade-off between memory consumption and computational cost. For instance on matrix Geo1438, Approach 2 uses three times as much memory as Approach 1 while being three times faster. Our new approach leads to an execution time only 30% larger than Approach 2 when given a memory 30% larger than the one needed by Approach 1.
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Equipe Roma Connect in order to contact the contributor
Submitted on : Friday, October 23, 2020 - 1:43:06 PM
Last modification on : Saturday, September 11, 2021 - 3:19:41 AM
Long-term archiving on: : Sunday, January 24, 2021 - 6:39:59 PM


Files produced by the author(s)


  • HAL Id : hal-02976233, version 1



Loris Marchal, Thibault Marette, Grégoire Pichon, Frédéric Vivien. Trading Performance for Memory in Sparse Direct Solvers using Low-rank Compression. [Research Report] RR-9368, INRIA. 2020. ⟨hal-02976233⟩



Record views


Files downloads