On Exploiting Sparsity of Multiple Right-Hand Sides in Sparse Direct Solvers

Résumé : Le coût des résolutions triangulaires des solveurs creux directs est parfois critique. Ce coût peut dépasser celui de la factorisation dans les applications qui nécessitent la résolution de plusieurs milliers de seconds membres. Cette étude se concentre sur les cas où les seconds membres sont multiples, creux et n’ont pas tous la même structure. Étant donnée la factorisation A = LU d’une matrice creuse A, l’étude met surtout l’accent sur la résolution du premier système triangulaire LY = B, où L est triangulaire inférieure. Dans ce type de problèmes, le creux dans la matrice B peut être exploité de deux manières. Premièrement, on évite le calcul de certaines lignes, ce qui correspond à élaguer certains nœuds de l’arbre d’élimination (qui représente les dépendances entre les calculs de la résolution). Deuxièmement, on réduit, pour chaque nœud, le calcul sur des sous-ensembles de colonnes de B plutôt que sur la matrice complète. Dans ce cas, un problème combinatoire doit être résolu afin de trouver une permutation des colonnes de B. S’appuyant d’abord sur l’algorithme de dissection emboîtée appliqué à un domaine régulier, un premier algorithme est proposé pour construire une permutation des colonnes de B. Puis une nouvelle approche permet de poursuivre la réduction du nombre d’opérations grâce à la création de blocs. Pour préserver la flexibilité de l’implémentation ainsi que l’efficacité des opérations de type BLAS 3, un nombre minimal de groupe est créé. Inspirés d’abord par des observations géométriques, ces nou- veaux algorithmes ont été étendus algébriquement pour n’utiliser que des informations provenant de la structure des seconds membres et des arbres d’élimination. Ils permettent ainsi une conver- gence rapide vers le nombre minimal d’opérations. Les résultats expérimentaux démontrent le gain obtenu par rapport à d’autres approches classiques. Enfin, les applications et extensions possibles de ce travail sont présentées.
Type de document :
Rapport
[Research Report] RR-9122, ENS de Lyon; INRIA Grenoble - Rhone-Alpes. 2017, pp.1-28
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01649244
Contributeur : Equipe Roma <>
Soumis le : mardi 5 décembre 2017 - 14:25:28
Dernière modification le : mercredi 12 septembre 2018 - 17:46:03

Fichier

on_exploiting_sparse_rhs_in_di...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01649244, version 2

Citation

Patrick Amestoy, Jean-Yves L'Excellent, Gilles Moreau. On Exploiting Sparsity of Multiple Right-Hand Sides in Sparse Direct Solvers. [Research Report] RR-9122, ENS de Lyon; INRIA Grenoble - Rhone-Alpes. 2017, pp.1-28. 〈hal-01649244v2〉

Partager

Métriques

Consultations de la notice

230

Téléchargements de fichiers

52