Skip to Main content Skip to Navigation

Prédiction de structure et algorithmique parallèle pour la factorisation LU des matrices creuses

Abstract : This dissertation treats of parallel numerical computing considering the Gaussian elimination, as it is used to solve large sparse nonsymmetric linear systems. Usually, computations on sparse matrices have an initial phase that predicts the nonzero structure of the output, which helps with memory allocations, set up data structures and schedule parallel tasks prior to the numerical computation itself. To this end, we study the structure prediction for the sparse LU factorization with partial pivoting. We are mainly interested to identify upper bounds as tight as possible to these structures. This structure prediction is then used in a phase called symbolic factorization, followed by a phase that performs the numerical computation of the factors, called numerical factorization. For very large matrices, a significant part of the overall memory space is needed by structures used during the symbolic factorization, and this can prevent a swap-free execution of the LU factorization. We propose and study a parallel algorithm to decrease the memory requirements of the nonsymmetric symbolic factorization. For an efficient parallel execution of the numerical factorization, we consider the analysis and the handling of the data dependencies graphs resulting from the processing of sparse matrices. This analysis enables us to develop scalable algorithms, which manage memory and computing resources in an effective way.
Document type :
File URL :
Complete list of metadatas
Contributor : Thèses Ul <>
Submitted on : Thursday, March 29, 2018 - 10:38:52 AM
Last modification on : Tuesday, December 15, 2020 - 12:22:53 PM


  • HAL Id : tel-01746486, version 1



Laura Grigori. Prédiction de structure et algorithmique parallèle pour la factorisation LU des matrices creuses. Autre [cs.OH]. Université Henri Poincaré - Nancy 1, 2001. Français. ⟨NNT : 2001NAN10264⟩. ⟨tel-01746486⟩



Record views