Contribution à l'algorithmique parallèle dans le domaine de l'algèbre linéaire creuse

Abstract

Dans ce travail, nous avons étudié la parallélisation des factorisations LU et de Cholesky, sur machines parallèles à mémoires distribuées, pour la résolution des systèmes linéaires creux. Tout d’abord, nous nous sommes intéressées à la parallélisation de la factorisation numérique LU des matrices creuses en considérant la structure finale de ces matrices, obtenues après les étapes de rémunération et de factorisation symbolique. Nous avons montré les inconvénients de la distribution bloc-cyclique et ensuite nous avons proposé une nouvelle distribution des données, basée sur une distribution dynamique à chaque étape de l’élimination, dans le but d’améliorer la distribution bloc-cyclique en terme d’équilibre de charge et du coût total d’exécution. Nous avons implémenté et testé cet algorithme sur deux systèmes parallèles, installés au Laboratoire LaRIA d’Amiens, à savoir un Cluster de PCs et un Cluster d’Alphas. Les résultats expérimentaux montrent l’avantage de notre nouvelle distribution comparée à la distribution bloc-cyclique. Ensuite nous nous sommes intéressées à l’étude de la parallélisation de la factorisation de Cholesky pour des matrices creuse, symétriques et définies positives. Nous avons proposé un algorithme parallèle pour les matrices qui proviennent de la discrétisation des EDP par la méthode de différences finies pour les problèmes 3D. L’algorithme proposé est de type multiphase et il est dédié aux machines d-reconfigurables. Nous avons montré, par une étude théorique, que le surcoût de communication est amélioré sur ce type de machines comparé au code multifrontal proposé dans la littérature pour un hypercube de processeurs.