Skip to Main content Skip to Navigation
Reports

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

Patrick Amestoy 1 Jean-Yves l'Excellent 2 Gilles Moreau 2
1 IRIT-APO - Algorithmes Parallèles et Optimisation
IRIT - Institut de recherche en informatique de Toulouse
2 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
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 deplusieurs milliers de seconds membres. Cette étude se concentre sur les cas où les seconds membressont 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 larésolution du premier système triangulaire LY = B, où L est triangulaire inférieure. Dans ce typede 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, pourchaque 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 colonnesde B.S’appuyant d’abord sur l’algorithme de dissection emboîtée appliqué à un domaine régulier, unpremier algorithme est proposé pour construire une permutation des colonnes de B. Puis une nouvelleapproche 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 provenantde 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 gainobtenu par rapport à d’autres approches classiques. Enfin, les applications et extensions possiblesde ce travail sont présentées.
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-01649244
Contributor : Equipe Roma <>
Submitted on : Tuesday, December 5, 2017 - 2:25:28 PM
Last modification on : Saturday, June 13, 2020 - 3:45:50 AM

File

on_exploiting_sparse_rhs_in_di...
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

595

Files downloads

1201