Cette thèse porte sur le partitionnement parallèle de graphes et essentiellement sur son application à la renumérotation de matrices<br />creuses.<br /><br />Nous utilisons pour résoudre ce problème un schéma multi-niveaux dont nous avons parallélisé les phases de contraction et d'expansion.<br /><br />Nous avons ainsi introduit pour la phase de contraction un nouvel algorithme de gestion des conflits d'appariements distants, tout en<br />améliorant les algorithmes déjà existants en leur associant une phase<br />de sélection des communications les plus utiles.<br /><br />Concernant la phase d'expansion, nous avons introduit la notion de graphe bande qui permet de diminuer de manière très conséquente la taille du problème à traiter par les algorithmes de raffinement. Nous avons généralisé l'utilisation de ce graphe bande aux implantations séquentielles et parallèles de notre outil de partitionnement Scotch.<br /><br />Grâce à la présence du graphe bande, nous avons proposé une utilisation nouvelle des algorithmes génétiques dans le cadre de<br />l'expansion en les utilisant comme heuristiques parallèles de raffinement de la partition.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00199898 |
| Date | 28 September 2007 |
| Creators | Chevalier, Cédric |
| Publisher | Université Sciences et Technologies - Bordeaux I |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0025 seconds