Skip to Main content Skip to Navigation
Theses

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 :
Theses
File URL :
http://docnum.univ-lorraine.fr/prive/SCD_T_2001_0264_GRIGORI.pdf
Complete list of metadata

https://hal.univ-lorraine.fr/tel-01746486
Contributor : Thèses Ul Connect in order to contact the contributor
Submitted on : Thursday, March 29, 2018 - 10:38:52 AM
Last modification on : Saturday, October 16, 2021 - 11:26:08 AM

Identifiers

  • HAL Id : tel-01746486, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

53