Block Low Rank Algebraic Clustering for Sparse Direct Solvers

Pierre Ramet 1
1 HiePACS - High-End Parallel Algorithms for Challenging Numerical Simulations
LaBRI - Laboratoire Bordelais de Recherche en Informatique, Inria Bordeaux - Sud-Ouest
Résumé : De nombreuses applications scientifiques comme l'électromagnétisme utilisent des mod-èles numériques qui reviennent à résoudre des systèmes linéaires creux de grande taille. Dans le cadre de cette présentation, on considère le solveur direct creux PaStiX [1]-développé depuis de nombreuses années dans l'équipe projet HiePACS d'Inria Bordeaux-dans l'objectif de réduire l'empreinte mémoire et le temps de résolution. L'objectif est d'introduire des techniques de compression low-rank pour résoudre des problèmes qui ne passent actuellement pas à l'échelle. Dans le contexte purement algébrique du solveur (au-cune connaissance de la géométrie dont est issu le problème), l'objectif est de prendre en entrée une précision requise par l'utilisateur et de fournir une solution à cette précision, la précision machine étant trop fine pour de nombreuses applications. Un solveur utilisant le format de compression Block Low-Rank (BLR) a été développé dans le cadre de la thèse de Grégoire Pichon. En pratique, les supernoeuds les plus volu-mineux sont redécoupés de manière à avoir un ensemble de supernoeuds de taille limitée (entre 128 et 256 dans nos expériences). A partir de cette partition raffinée, l'ensemble des blocs extra-diagonaux suffisamment volumineux sont compressés en format low-rank avec la décomposition en valeurs singulières (SVD) ou l'algorithme Rank-Revealing QR (RRQR). Deux versions du solveur low-rank ont été développées. La stratégie Minimal Memory permet de réduire l'empreinte mémoire avec un surcoût en temps limité. L'intérêt principal est que des problèmes qui étaient trop volumineux pour être résolus auparavant peuvent maintenant passer en mémoire. La seconde stratégie, Just-In-Time permet de réduire le temps de résolution, sans avoir d'impact important sur la consommation mémoire [2]. Disposant d'une version BLR fonctionnelle qui apporte des gains en temps ou en mémoire intéressants, nous nous sommes intéressés à plusieurs optimisations : Étude du clustering des inconnues Une des problématiques de la compression low-rank est le clustering des inconnues. En effet, les séparateurs issus de la dissection emboîtée doivent être redécoupés en un ensemble de blocs pour exhiber la nouvelle partition low-rank. Une approche classique consiste à effectuer un kway partitionnement sur les séparateurs, pour former des clusters compacts avec peu de voisins. Cependant, une telle approche ne prend pas en compte les contributions qui vont arriver sur ce séparateur. Nous étudions actuellement de nouvelles heuristiques pour isoler de bons clusters dans le séparateur ainsi qu'un ensemble d'éléments pas (ou peu) compressibles. L'étude actuelle montre des gains en temps et en mémoire [3] (soumis à SIMAX). Étude de l'ordering des inconnues L'étude de l'ordering des inconnues, actuellement réalisée avec la dissection emboîtée au travers du partitionneur Scotch, pourrait permettre d'exhiber des blocs plus compressibles. Les techniques de partitionnement actuelles ont pour objectif de réduire le remplissage tout en garantissant un bon niveau de parallélisme. En les couplant avec des critères sur la compression (i.e., des distances dans le graphe), il est imaginable de fournir une meilleure numérotation des inconnues dans un contexte de compression low-rank [4].
Complete list of metadatas

Cited literature [7 references]  Display  Hide  Download

https://hal.inria.fr/hal-02139186
Contributor : Pierre Ramet <>
Submitted on : Friday, May 24, 2019 - 2:57:07 PM
Last modification on : Wednesday, May 29, 2019 - 1:50:21 AM

File

joso.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02139186, version 1

Citation

Pierre Ramet. Block Low Rank Algebraic Clustering for Sparse Direct Solvers. JOSO 2019 - Journées Ondes Sud-Ouest, Mar 2019, Le Barp, France. ⟨hal-02139186⟩

Share

Metrics

Record views

37

Files downloads

489