[JOB] PhD. – Multigrid algorithms tuning using AI for the solution of linear systems

Etablissement : Université Paris-Saclay GS Ingormatique et sciences du numérique
École doctorale : Sciences et Technologies de l’nformation et de la Communication
Spécialité : Informatique mathématique
Unité de recherche : Mdls – Maison de la Simulation

Encadrement de la thèse : Nahid EMAD PETITON
Co-Directeur : Thomas DUFAUD

Description de la problématique de recherche – Project description

La performance des simulateurs a un impact direct à la fois sur la qualité des résultats de simulation, avec la précision souhaitée et sur la capacité d’explorer une grande variété d’hypothèses scientifiques. Dans un grand nombre de simulateurs numériques, la résolution de systèmes linéaires, très souvent mal conditionnés, constitue l’étape la plus consommatrice en temps de calcul (jusqu’à 80% de la simulation).

Les méthodes multigrilles font partie des solveurs et des préconditionneurs efficaces et puissants pour la résolution de grands systèmes linéaires mal conditionnés. Cependant, le paramétrage optimal de ces méthodes ; tels que l’algorithme de lissage, les schémas de correction, le choix des opérateurs de restriction dépend du problème à traiter et oriente fortement l’efficacité numérique de cette famille de méthodes. De plus, il existe plusieurs algorithmes multigrilles, comprenant différents algorithmes de lissage tels que Jacobi et Gauss- Seidel, différents schémas de correction tels que V-Cycle, W-Cycle et différents opérateurs de prolongation/restriction. Le choix des différents algorithmes et le réglage fin de ces paramètres améliore le taux de convergence de cette famille de méthode et influence le temps de calcul sur l’architecture cible type CPU, GPU ou TPU. L’expertise de l’utilisateur dans la sélection des paramètres est critique pour une utilisation optimale de ces méthodes.

En partant de ce constat, l’objectif du travail de recherche proposé est de concevoir et d’utiliser des techniques d’apprentissage afin de trouver pour la méthode multigrille algébrique de meilleurs paramétrages à la fois pour les problèmes linéaires et non linéaires à 2-3 dimensions. Les études ciblées seront issues de deux grandes catégories de simulations : la dynamique des fluides et l’écoulement en milieu poreux. Parmi les applications sélectionnées, nous pouvons évoquer les modélisations Fluide-particules, Géomécanique, et séquestration du Co2, avec pour chacune des systèmes différents à résoudre.

Simulator performance has a direct impact both on the quality of simulation results, with the desired accuracy, and on the ability to explore a wide variety of scientific hypotheses. In a large number of numerical simulators, the resolution of linear systems, which are very often poorly conditioned, is the most time-consuming stage of the process (up to 80% of the simulation).
Multigrid methods are among the most efficient and powerful solvers and preconditioners for solving large, ill-conditioned linear systems. However, the optimal parameterization of these methods, such as the smoothing algorithm, the correction schemes and the choice of restriction operators, depends on the problem to be solved and strongly influences the numerical efficiency of this family of methods. In addition, there are several multigrid algorithms, including different smoothing algorithms such as Jacobi and Gauss-Seidel, different correction schemes such as V-Cycle, W-Cycle and different extension/restriction operators. The choice of different algorithms and the fine-tuning of these parameters improves the convergence rate of this family of methods and influences the computation time on the target CPU, GPU or TPU architecture. User expertise in parameter selection is critical for optimal use of these methods.
With this in mind, the aim of the proposed research work is to design and use learning techniques to find better parameterizations for the algebraic multigrid method, for both linear and non-linear 2-3-dimensional problems. The targeted studies will be drawn from two broad categories of simulations: fluid dynamics and porous media flow. Selected applications include fluid-particle modeling, geomechanics and Co2 sequestration, each with different systems to solve.

Context

La simulation numérique est un outil complémentaire aux études expérimentales permettant de comprendre finement les phénomènes physiques complexes. C’est aussi une aide importante pour la mise au point et l’évaluation de solutions techniques innovantes et prospectives. Elle est ainsi au cœur de nombreux domaines tels que la mécanique des fluides, la conception de matériaux ou les géosciences.

Dans un grand nombre de simulateurs numériques, la résolution de systèmes linéaires, très souvent mal conditionnés, constitue l’étape la plus consommatrice en temps de calcul (jusqu’à 80% de la simulation). Les préconditionneurs employés voient leurs performances variées en fonction des paramètres choisis. L’expertise de l’utilisateur dans la sélection des paramètres est ainsi nécessaire pour une utilisation optimale de ces méthodes.

Dans ce projet, nous nous intéressons aux systèmes linéaires issus de la discrétisation d’un problème de poisson à coefficients variables. Ce problème est au cœur de nombreuses méthodes numériques pour la simulation d’écoulements de type Darcy ou Navier-Stockes. Les méthodes multigrilles algébriques (AMG) sont parmi les plus efficaces pour résoudre les systèmes linéaires associés à la discrétisation de cette équation sur des maillages non structurés. Ces méthodes emploient des opérateurs de “smoothing” pour réduire les composantes à haute fréquence de l’erreur, des opérateurs de restriction pour projeter le problème sur des grilles grossières et enfin des opérateurs de prolongation pour revenir sur les tailles de grilles fines initiales. Chacune de ces étapes, ainsi que leur ordonnancement en cycles, dispose de nombreux paramètres à sélectionner (type de smoother et nombre d’itérations, choix des opérateurs de restriction et prolongation pour tenir compte de la variabilité des coefficients de l’équation, ou encore agencement des cycles multigrilles) (Briggs et al.). Le paramétrage optimal de ces méthodes dépend fortement du problème physique modélisé et représente une difficulté importante dans leur adoption.

Il est ainsi nécessaire de développer des méthodes d’apprentissage permettant d’accélérer la convergence des méthodes multigrilles, soit en obtenant un paramétrage optimal de méthodes existantes, soit en imitant directement les méthodes existantes. De nombreux travaux récents se sont engagés dans ces deux voies :
– Opérateurs de projection : (Katrutsa et al.) et (Greenfeld et al.) proposent des méthodes d’apprentissage non supervisées pour optimiser le paramétrage des opérateurs de prolongation et restriction des méthodes multigrilles géométriques (GMG) à deux niveaux avec une fonction coût permettant de minimiser le rayon spectral de la matrice d’itération. (Luz et al.) étendent ces travaux à des méthodes AMG en utilisant des Graph Neural Networks (GNN) pour gérer les maillages non structurés.

– Smoother : (Hsieh et al.) proposent une méthode d’apprentissage supervisée basée sur des Convolutional Neural Networks (CNN) et l’architecture U-Net afin d’apprendre une correction à l’algorithme de Jacobi tout en conservant les garanties de convergence. (Huang et al.) étendent ces travaux à l’optimisation du smoother de Jacobi dans les méthodes GMG.
Ces travaux s’appuient notamment sur le parallèle développé par (He et al.) entre les méthodes multi-grilles et les réseaux de convolution. En effet, le passage d’une grille grossière à une grille fine (et inversement) peut être vu comme une étape de filtrage d’un CNN.

Les résultats observés montrent une accélération d’un facteur 2 à 10 de la convergence des algorithmes existants tout en conservant d’excellentes propriétés de généralisation. Cependant, ces travaux sont limités à des étapes spécifiques des méthodes multigrilles et ont pour cible principale les méthodes GMG, restreignant leur utilisation aux maillages structurés sur des problèmes simplifiés.
L’objectif principal de ce travail de thèse est de développer des méthodes d’apprentissage pour la résolution des systèmes linéaires préconditionnés issus de la discrétisation sur maillages non structurés du problème de Poisson à coefficients variables. Ces méthodes doivent permettre d’accélérer la convergence des algorithmes multigrilles sur des architectures matérielles hétérogènes.

La simulation numérique est un outil complémentaire aux études expérimentales permettant de comprendre finement les phénomènes physiques complexes. C’est aussi une aide importante pour la mise au point et l’évaluation de solutions techniques innovantes et prospectives. Elle est ainsi au cœur de nombreux domaines tels que la mécanique des fluides, la conception de matériaux ou les géosciences.

Dans un grand nombre de simulateurs numériques, la résolution de systèmes linéaires, très souvent mal conditionnés, constitue l’étape la plus consommatrice en temps de calcul (jusqu’à 80% de la simulation). Les préconditionneurs employés voient leurs performances variées en fonction des paramètres choisis. L’expertise de l’utilisateur dans la sélection des paramètres est ainsi nécessaire pour une utilisation optimale de ces méthodes.

Dans ce projet, nous nous intéressons aux systèmes linéaires issus de la discrétisation d’un problème de poisson à coefficients variables. Ce problème est au cœur de nombreuses méthodes numériques pour la simulation d’écoulements de type Darcy ou Navier-Stockes. Les méthodes multigrilles algébriques (AMG) sont parmi les plus efficaces pour résoudre les systèmes linéaires associés à la discrétisation de cette équation sur des maillages non structurés. Ces méthodes emploient des opérateurs de “smoothing” pour réduire les composantes à haute fréquence de l’erreur, des opérateurs de restriction pour projeter le problème sur des grilles grossières et enfin des opérateurs de prolongation pour revenir sur les tailles de grilles fines initiales. Chacune de ces étapes, ainsi que leur ordonnancement en cycles, dispose de nombreux paramètres à sélectionner (type de smoother et nombre d’itérations, choix des opérateurs de restriction et prolongation pour tenir compte de la variabilité des coefficients de l’équation, ou encore agencement des cycles multigrilles) (Briggs et al.). Le paramétrage optimal de ces méthodes dépend fortement du problème physique modélisé et représente une difficulté importante dans leur adoption.

Il est ainsi nécessaire de développer des méthodes d’apprentissage permettant d’accélérer la convergence des méthodes multigrilles, soit en obtenant un paramétrage optimal de méthodes existantes, soit en imitant directement les méthodes existantes. De nombreux travaux récents se sont engagés dans ces deux voies :
– Opérateurs de projection : (Katrutsa et al.) et (Greenfeld et al.) proposent des méthodes d’apprentissage non supervisées pour optimiser le paramétrage des opérateurs de prolongation et restriction des méthodes multigrilles géométriques (GMG) à deux niveaux avec une fonction coût permettant de minimiser le rayon spectral de la matrice d’itération. (Luz et al.) étendent ces travaux à des méthodes AMG en utilisant des Graph Neural Networks (GNN) pour gérer les maillages non structurés.

– Smoother : (Hsieh et al.) proposent une méthode d’apprentissage supervisée basée sur des Convolutional Neural Networks (CNN) et l’architecture U-Net afin d’apprendre une correction à l’algorithme de Jacobi tout en conservant les garanties de convergence. (Huang et al.) étendent ces travaux à l’optimisation du smoother de Jacobi dans les méthodes GMG.
Ces travaux s’appuient notamment sur le parallèle développé par (He et al.) entre les méthodes multi-grilles et les réseaux de convolution. En effet, le passage d’une grille grossière à une grille fine (et inversement) peut être vu comme une étape de filtrage d’un CNN.

Les résultats observés montrent une accélération d’un facteur 2 à 10 de la convergence des algorithmes existants tout en conservant d’excellentes propriétés de généralisation. Cependant, ces travaux sont limités à des étapes spécifiques des méthodes multigrilles et ont pour cible principale les méthodes GMG, restreignant leur utilisation aux maillages structurés sur des problèmes simplifiés.

L’objectif principal de ce travail de thèse est de développer des méthodes d’apprentissage pour la résolution des systèmes linéaires préconditionnés issus de la discrétisation sur maillages non structurés du problème de Poisson à coefficients variables. Ces méthodes doivent permettre d’accélérer la convergence des algorithmes multigrilles sur des architectures matérielles hétérogènes.
Références :

(Briggs et al.) William Briggs, Van Henson and Steve McCormick. A Multigrid Tutorial, 2nd Edition, SIAM, (2000) ISBN: 9780898714623. (Huang et al.) Ru Huang, Ruipeng Li and Yuanzhe Xi. Learning optimal multigrid smoothers via neural networks, (2021) arXiv:2102.1207v1 (Katrutsa et al.) Alexandr Katrutsa, Talgat Daulbaev and Ivan Oseledets. Deep Multigrid: learning prolongation and restriction matrices, (2017) arXiv:1711.03825v1.

(He et al.) Juncai He and Jinchao Xu. MgNet: A unified framework of multigrid and convolutional neural network. Sci. China Math. (2019). https://doi.org/10.1007/s11425-019-9547-2
(Hsieh et al.) Jun-Ting Hsieh, Shengjia Zhao, Stephan Eismann, Lucia Mirabella and Stefano Ermon. Learning Neural PDE Solvers with Convergence Guarantees (2019). arXiv:1906.01200v1

(Greenfeld et al.) Daniel Greenfeld, Meirav Galun, Ron Kimmel, Irad Yavneh and Ronen Basri. Learning to Optimize Multigrid PDE Solvers. ICML (2019). arXiv:1902.10248
(Luz et al.) Ilay Luz, Meirav Galun, Haggai Maron, Ronen Basri and Irad Yavneh. Learning Algebraic Multigrid Using Graph Neural Networks (2020). arXiv:2003.05744

Objectifs

L’objectif principal de ce travail de thèse est de développer des méthodes d’apprentissage pour la résolution des systèmes linéaires préconditionnés issus de la discrétisation sur maillages non structurés du problème de Poisson à coefficients variables. Ces méthodes doivent permettre d’accélérer la convergence des algorithmes multigrille sur des architectures matérielles hétérogènes.

Méthode

Afin de répondre à l’objectif fixé, nous proposons un plan de travail en 4 étapes :
– Etat de l’art des méthodes multigrilles améliorée par l’IA : Il s’agit dans un premier temps de faire un inventaire des méthodes d’accélération de chaque étape des algorithmes multigrilles. Il faudra évaluer leur impact en analysant les taux de convergence et le rayon spectral des opérateurs de transfert d’erreur résultants. Les travaux porteront d’abord sur des maillages structurés (réseau CNN) puis sur des maillages non structurés (réseau GNN)
– Conception d’un solveur linéaire multigrille hybride par composant : Sur la base des travaux précédents, il s’agira ensuite de proposer un choix de méthode d’apprentissage pour accélérer chaque étape du solveur multigrille (smoother, opérateurs de projection, niveaux de grille et type de cycle). Ces méthodes seront entraînées de manière indépendante puis assemblées lors de l’évaluation du modèle.
– Conception d’un solveur linéaire multigrille global : L’optimisation de chaque paramètre n’est pas complètement indépendante des autres composantes: une fois l’approche par bloc établie, on cherchera à enchaîner directement les étapes du solveur multigrille hybride dans un entraînement global.
– Développement d’un framework général de solveur linéaire hybride : Les méthodes de préconditionnement construites à partir des méthodes de déflation, de décomposition de domaine ou multigrille ont des équivalences (Tang et al., DOI:10.1007/s10915-009-9272-6). L’objectif sera d’adapter les méthodologies développées précédemment pour accélérer ces divers types de méthodes.
L’efficacité des méthodes développées sera évaluée sur des applications industrielles telles que les modélisations des interactions Fluide-particules, la Géomécanique, ou la séquestration du Co2, avec chacune des systèmes linéaires à résoudre ayant des caractéristiques différentes.
Nous évaluons la généralisation de ces méthodes sur un ensemble de paramètres de simulation variables : problème physique sous- jacent, géométrie du domaine, conditions aux bord ou encore taille initiale de la grille.

Résultats attendus – Expected results

La première cible de la thèse est l’élaboration et la validation de la solution proposée. Ces composants logiciels seront dans un premier temps intégrés dans une bibliothèque écrite dans des frameworks spécifiques (Tensorflow, Pytorch, JAX) permettant de bénéficier directement d’une performance optimisée sur les architectures matérielles de type CPU, GPU voire TPU.
Cette solution pourra également être interfacée dans les bibliothèques telles que Trilinos et AMGX ce qui nous permettra d’avoir des solutions performantes de référence à la fois sur CPU et GPU. Son efficacité et sa portabilité seront ensuite évaluées dans les simulations de la dynamique des fluides et l’écoulement en milieu poreux.