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).
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/hal-01597072
Contributor : Aurélien Falco <>
Submitted on : Thursday, September 28, 2017 - 10:38:59 AM
Last modification on : Monday, May 27, 2019 - 11:54:02 AM
Long-term archiving on : Friday, December 29, 2017 - 2:29:48 PM

File

report.pdf
Files produced by the author(s)

Identifiers

  • 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. ⟨hal-01597072⟩

Share

Metrics

Record views

250

Files downloads

348