Vers une factorisation symbolique hiérarchique de rang faible pour des matrices creuses

Emmanuel Agullo 1 Aurélien Falco 1 Luc Giraud 1 Guillaume Sylvand 1
1 HiePACS - High-End Parallel Algorithms for Challenging Numerical Simulations
LaBRI - Laboratoire Bordelais de Recherche en Informatique, Inria Bordeaux - Sud-Ouest
Résumé : Les algorithmes hiérarchiques basés sur des techniques de compression de rang faible ont ré-volutionné les méthodes de résolution de systèmes linéaires denses à l'aube du XXIème siècle en réduisant considérablement les coûts de calcul. Toutefois, leur application au traitement de systèmes linéaires creux (comportant de nombreux éléments nuls), qui sont le type de pro-blèmes apparaissant le plus souvent au coeur des simulations numériques, reste aujourd'hui un challenge majeur auquel s'attellent à la fois la communauté des matrices hiérarchiques et celle des matrices creuses. À cet effet, une première classe d'approche a été développée par la communauté des matrices hiérarchiques pour exploiter la structure creuse des matrices. Si le point fort de ces méthodes est que l'algorithme résultant reste hiérarchique, celles-ci ne par-viennent pas à exploiter certains zéros comme le font naturellement les méthodes classiques de factorisation de systèmes linéaires creux. À l'opposé, du fait qu'une factorisation creuse peut être vue comme une séquence de plus petites opérations denses, la communauté des matrices creuses a exploré cette propriété pour introduire des techniques hiérarchiques au sein de ces opérations élémentaires. Cependant, l'algorithme résultant perd la propriété fondamentale des algorithmes hiérarchiques, dans la mesure où la hiérarchie de compression est seulement locale. Dans cet article, nous introduisons un nouvel algorithme, effectuant une factorisation symbolique creuse hiérarchique qui permet d'exploiter efficacement l'ensemble des zéros de la matrice creuse et de ses facteurs tout en préservant une structure hiérarchique globale. Nous montrons expérimentalement que cette nouvelle approche permet d'obtenir à la fois un nombre réduit d'opérations (du fait de son caractère hiérarchique) et un nombre d'éléments non nuls aussi réduit qu'une méthode creuse (grâce au recours à une factorisation symbolique).
Type de document :
Communication dans un congrès
Conférence d’informatique en Parallélisme, Architecture et Système (ComPAS'17), Jun 2017, Sophia Antipolis, France. 2017, 〈https://compas2017.sciencesconf.org/〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01597072
Contributeur : Aurélien Falco <>
Soumis le : jeudi 28 septembre 2017 - 10:38:59
Dernière modification le : jeudi 11 janvier 2018 - 08:44:23
Document(s) archivé(s) le : vendredi 29 décembre 2017 - 14:29:48

Fichier

report.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01597072, version 1

Citation

Emmanuel Agullo, Aurélien Falco, Luc Giraud, Guillaume Sylvand. Vers une factorisation symbolique hiérarchique de rang faible pour des matrices creuses. Conférence d’informatique en Parallélisme, Architecture et Système (ComPAS'17), Jun 2017, Sophia Antipolis, France. 2017, 〈https://compas2017.sciencesconf.org/〉. 〈hal-01597072〉

Partager

Métriques

Consultations de la notice

177

Téléchargements de fichiers

63