Consolidation d'un cadre unifié pour les algorithmes hiérarchiques de matrices de rang faible

Ce travail introduit une abstraction commune permettant d’exprimer aussi bien les H-matrices que les méthodes FMM au sein d’un même algorithme générique. Cette approche a été implémentée dans la bibliothèque Composyx, développée à Inria.

Environnement logiciel

Les développements seront réalisés dans la bibliothèque Composyx, une bibliothèque C++ développée à Inria permettant l’expression modulaire d’algorithmes numériques.

Mission confiée

Objectifs du relais-thèse

L’objectif principal de ce relais-thèse est de consolider ces premiers résultats, tant sur le plan algorithmique que logiciel. Dans un premier temps, le ou la candidate montera en compétence sur :

• les méthodes hiérarchiques (FMM, H-matrices et variantes) ;
• leurs principes mathématiques et algorithmiques ;
• leur implémentation dans la bibliothèque Composyx.

Le travail consistera ensuite à renforcer la validation expérimentale du cadre proposé à travers :

• la réalisation d’une campagne plus large de tests numériques ;
• l’étude des performances de l’implémentation générique ;
• la comparaison avec des implémentations de référence, notamment hmat-oss pour les H-matrices et ScalFMM pour la FMM, en exécution séquentielle ;
• l’identification des points forts et des limites de l’approche proposée afin de consolider les résultats obtenus.

Ce travail contribuera à renforcer la maturité scientifique et logicielle du cadre unifié développé dans Composyx.

Perspectives (si le temps le permet)

Selon l’avancement du projet, deux pistes pourront être explorées. Vers une factorisation hiérarchique unifiée. Le cadre actuel concerne le produit matrice-vecteur. Une première extension consisterait à étudier dans quelle mesure les principes de composition proposés peuvent être adaptés aux algorithmes de factorisation. Si les factorisations hiérarchiques sont bien établies pour les H-matrices, leur équivalent n’existe pas véritablement dans le contexte des méthodes FMM. Cette piste vise à étudier la faisabilité d’une approche unifiée. Vers une implémentation parallèle. Une seconde perspective concerne le parallélisme. Une implémentation fondée sur un modèle de programmation à base de tâches pourrait être développée en s’appuyant sur STF, éventuellement exprimé en STF++ (développé dans le cadre du projet NumPEX Exa-Soft), avec une exécution déléguée au runtime StarPU., * Étudier les algorithmes hiérarchiques de compression de matrices (FMM, H-matrices et variantes) ainsi que leur implémentation dans la bibliothèque Composyx.

• Concevoir, développer et faire évoluer les composants C++ du cadre générique de calcul hiérarchique au sein de Composyx.
• Concevoir et réaliser une campagne de tests numériques et de mesures de performances afin de valider et consolider l’approche proposée.
• Comparer les performances et les propriétés de l’implémentation générique avec des bibliothèques de référence (notamment hmat-oss et ScalFMM).
• Analyser les résultats expérimentaux et proposer des améliorations algorithmiques ou logicielles lorsque cela est pertinent.

Activités complémentaires

• Participer à la rédaction de rapports techniques et de publications scientifiques.
• Présenter l’avancement des travaux lors des réunions de l’équipe et de séminaires scientifiques.
• Explorer, si le temps le permet, de nouvelles perspectives telles qu’une factorisation hiérarchique unifiée ou une implémentation parallèle à base de tâches (STF++/StarPU).

• une curiosité pour le calcul numérique, l’algèbre linéaire et les méthodes scientifiques ;
• un intérêt pour les algorithmes performants et les méthodes hiérarchiques ;
• de bonnes compétences en programmation C++ ;
• des connaissances en calcul haute performance (HPC) ;
• une capacité à lire des articles scientifiques et à contribuer à un développement logiciel de recherche.

Des connaissances en algèbre linéaire numérique, méthodes de compression de matrices ou programmation parallèle constitueront un plus, sans être indispensables., Curieux(se) et motivé(e) par le calcul scientifique, vous appréciez comprendre les fondements mathématiques des algorithmes autant que leur mise en œuvre logicielle. Vous aimez développer des logiciels de recherche en C++, expérimenter, analyser les performances et confronter vos résultats à l’état de l’art. Une appétence pour l’algèbre linéaire numérique, les méthodes hiérarchiques ou le calcul haute performance constituera un atout, mais l’envie d’apprendre, la rigueur scientifique et le goût du travail en équipe sont avant tout les qualités qui permettront de réussir cette mission.

• Restauration subventionnée
• Transports publics remboursés partiellement
• Congés: 7 semaines de congés annuels + 10 jours de RTT (base temps plein) + possibilité d’autorisations d’absence exceptionnelle (ex : enfants malades, déménagement)
• Possibilité de télétravail et aménagement du temps de travail
• Équipements professionnels à disposition (visioconférence, prêts de matériels informatiques, etc.)
• Prestations sociales, culturelles et sportives (Association de gestion des œuvres sociales d’Inria)
• Accès à la formation professionnelle
• Sécurité sociale

Les méthodes hiérarchiques constituent aujourd’hui un outil incontournable pour accélérer les calculs sur de grandes matrices issues de simulations scientifiques. Elles permettent de réduire significativement les coûts en mémoire et en calcul en exploitant la structure de rang faible des interactions éloignées. Parmi les principales approches figurent les H-matrices (algébriques) et les méthodes analytiques de type Fast Multipole Method (FMM). Bien que développées par des communautés différentes, ces approches reposent sur des principes communs : partitionnement hiérarchique, critères d’admissibilité, approximations de rang faible et organisation des bases. Les mettre en évidence ouvre la voie à des implémentations plus génériques, modulaires et réutilisables. Dans ce contexte, un récent travail de recherche a proposé un cadre unifié et composable pour le produit matrice-vecteur hiérarchique : Emmanuel Agullo, Bérenger Bramas, Olivier Coulaud, Antoine Gicquel. Unified and Composable Rank-Structured Hierarchical Matrix-Vector Multiplication. RR-9611, Inria, 2026., Inria est l’institut national de recherche dédié aux sciences et technologies du numérique. Il emploie 2600 personnes. Ses 215 équipes-projets agiles, en général communes avec des partenaires académiques, impliquent plus de 3900 scientifiques pour relever les défis du numérique, souvent à l’interface d’autres disciplines. L’institut fait appel à de nombreux talents dans plus d’une quarantaine de métiers différents. 900 personnels d’appui à la recherche et à l’innovation contribuent à faire émerger et grandir des projets scientifiques ou entrepreneuriaux qui impactent le monde. Inria travaille avec de nombreuses entreprises et a accompagné la création de plus de 200 start-up. L’institut s’efforce ainsi de répondre aux enjeux de la transformation numérique de la science, de la société et de l’économie.