Le sujet de cette thèse est le développement de méthodes itératives permettant la résolution degrands systèmes linéaires creux d'équations présentant plusieurs seconds membres simultanément. Ces méthodes seront en particulier utilisées dans le cadre d'une application géophysique : la migration sismique visant à simuler la propagation d'ondes sous la surface de la terre. Le problème prend la forme d'une équation d'Helmholtz dans le domaine fréquentiel en trois dimensions, discrétisée par des différences finies et donnant lieu à un système linéaire creux, complexe, non-symétrique, non-hermitien. De plus, lorsque de grands nombres d'onde sont considérés, cette matrice possède une taille élevée et est indéfinie. Du fait de ces propriétés, nous nous proposons d'étudier des méthodes de Krylov préconditionnées par des techniques hiérarchiques deux niveaux. Un tel pre-conditionnement s'est montré particulièrement efficace en deux dimensions et le but de cette thèse est de relever le défi de l'adapter au cas tridimensionel. Pour ce faire, des méthodes de Krylov sont utilisées à la fois comme lisseur et comme méthode de résolution du problème grossier. Ces derniers choix induisent l'emploi de méthodes de Krylov dites flexibles. / The topic of this PhD thesis is the development of iterative methods for the solution of large sparse linear systems of equations with possibly multiple right-hand sides given at once. These methods will be used for a specific application in geophysics - seismic migration - related to the simulation of wave propagation in the subsurface of the Earth. Here the three-dimensional Helmholtz equation written in the frequency domain is considered. The finite difference discretization of the Helmholtz equation with the Perfect Matched Layer formulation produces, when high frequencies are considered, a complex linear system which is large, non-symmetric, non-Hermitian, indefinite and sparse. Thus we propose to study preconditioned flexible Krylov subspace methods, especially minimum residual norm methods, to solve this class of problems. As a preconditioner we consider multi-level techniques and especially focus on a two-level method. This twolevel preconditioner has shown efficient for two-dimensional applications and the purpose of this thesis is to extend this to the challenging three-dimensional case. This leads us to propose and analyze a perturbed two-level preconditioner for a flexible Krylov subspace method, where Krylov methods are used both as smoother and as approximate coarse grid solver.

Cette thèse porte sur le développement d’une méthode multigrilles parallèle visant à réduire les temps de calculs des simulations éléments finis dans le domaine de la mise en forme de pièces forgées en 3D. Ces applications utilisent une méthode implicite, caractérisées par une formulation mixte en vitesse/pression et une gestion du contact par pénalisation. Elles impliquent de grandes déformations qui rendent nécessaires des remaillages fréquents sur les maillages tétraédriques non structurés utilisés. La méthode multigrilles développée suit une approche hybride, se basant sur une construction géométrique des niveaux grossiers par déraffinement de maillage non emboîtés et sur une construction algébrique des systèmes linéaires intermédiaires et grossiers. Un comportement asymptotique quasi-linéaire et une bonne efficacité parallèle sont attendus afin de permettre la réalisation de simulations à grand nombre de degrés de liberté dans des temps plus raisonnables qu’aujourd’hui. Pour cela, l’algorithme de déraffinement de maillages est compatible avec le calcul parallèle, ainsi que les opérateurs permettant les transferts de champs entre les différents niveaux de maillages partitionnés. Les spécificités des problèmes à traiter ont mené à la sélection d'un lisseur plus complexe que ceux utilisés plus fréquemment dans la littérature. Sur la grille la plus grossière, une méthode de résolution directe est utilisée, en séquentiel comme en calcul parallèle. La méthode multigrilles est utilisée en tant que préconditionneur d’une méthode de résidu conjugué et a été intégrée au logiciel FORGE NxT et montre un comportement asymptotique et une efficacité parallèle proches de l’optimal. Le déraffinement automatique de maillages permet une compatibilité avec les remaillages fréquents et permet à la méthode multigrilles de simuler un procédé du début à la fin. Les temps de calculs sont significativement réduits, même sur des simulations avec des écoulements particuliers, sur lesquelles la méthode multigrilles ne peut être utilisée de manière optimale. Cette robustesse permet, par exemple, de réduire de 4,5 à 2,5 jours le temps de simulation d’un procédé. / A parallel multigrid method is developed to reduce large computational costs involved by the finite element simulation of 3D metal forming applications. These applications are characterized by a mixed velocity/pressure implicit formulation with a penalty formulation to enforce contact and lead to large deformations, handled by frequent remeshings of unstructured meshes of tetrahedral. The developed multigrid method follows a hybrid approach where the different levels of non-nested meshes are geometrically constructed by mesh coarsening, while the linear systems of the intermediate and coarse levels result from the algebraic approach. A close to linear asymptotical behavior is expected along with parallel efficiency in order to allow simulations with large number of degrees of freedom under reasonable computation times. These objectives lead to a parallel mesh coarsening algorithm and parallel transfer operators allowing fields transfer between the different levels of partitioned meshes. Physical specificities of metal forming applications lead to select a more complex multigrid smoother than those classically used in literature. A direct resolution method is used on the coarsest mesh, in sequential and in parallel computing. The developed multigrid method is used as a preconditioner for a Conjugate Residual algorithm within FORGE NxT software and shows an asymptotical behavior and a parallel efficiency close to optimal. The automatic mesh coarsening algorithm enables compatibility with frequent remeshings and allows the simulation of a forging process from beginning to end with the multigrid method. Computation times are significantly reduced, even on simulations with particular material flows on which the multigrid method is not optimal. This robustness allows, for instance, reducing from 4.5 to 2.5 days the computation of a forging process.

A study of the flowfield around axisymmetric launch vehicles in different flight conditions and configurations is performed in this work. Particularly, the VLS second stage flight configuration is analyzed considering the case with and without a propulsive jet in the vehicle base. Among the different cases considered for this configuration there are inviscid as well as viscous turbulent flows. The study is performed using a finite volume cell centered formulation on unstructured grids. Different spatial discretization schemes are compared, including a centered and an upwind scheme. The upwind scheme is a second-order version of the Liou flux vector splitting scheme and a simple scalar advection test problem is used to assess the influence of different reconstruction and limiting methods in the second-order extension of the scheme. Turbulence effects are accounted for using two one-equation turbulence closure models, namely the Baldwin and Barth and the Spalart and Allmaras models. An agglomeration multigrid algorithm is used to accelerate the convergence to steady state of the numerical solutions. Mesh refinement procedures as well as hybrid and adaptive meshes are discussed.

Avec le développement des techniques d’imagerie telles que la tomographie par rayons X au cours des dernières années, il est maintenant possible de prendre en compte la microstructure réelle dans les simulations des matériaux composites. Cependant, la complexité des composites tels que des fibres inclinées et brisées, les vides, exige un grand nombre des données à l’échelle microscopique pour décrire ces détails et amène ainsi des problèmes difficiles en termes de temps de calcul et de mémoire lors de l’utilisation de méthodes de simulation traditionnelles comme la méthode Eléments Finis. Ces problèmes deviennent encore plus sérieux dans la simulation de l’endommagement, comme la propagation des fissures. Par conséquent, il est nécessaire d’étudier des méthodes numériques plus efficaces pour ce genre de problèmes à grande échelle. La méthode Multigrille (MG) est une méthode qui peut être efficace parce que son coût de calcul est proportionnel au nombre d’inconnues. Dans cette thèse, un solveur de MG efficace pour ces problèmes est développé. La méthode MG est appliquée pour résoudre le problème d’élasticité statique basé sur l’équation de Lamé et aussi le problème de la propagation de fissures basé sur une méthode de champ de phase. La précision des solutions MG est validée par une solution analytique classique d’Eshelby. Ensuite, le solveur MG est développé pour étudier le processus d’homogénéisation des composites et ses solutions sont comparées avec des solutions existantes de la littérature. Après cela, le programme de calcul MG est appliqué pour simuler l’effet de bord libre dans les matériaux composites stratifiés. Une structure stratifiée réelle donnée par tomographie X est d’abord simulé. Enfin, le solveur MG est encore développé, combinant une méthode de champ de phase, pour simuler la rupture quasi-fragile. La méthode MG présente l’efficacité à la fois en temps de calcul et en mémoire pour résoudre les problèmes ci-dessus. / With the development of imaging techniques like X-Ray tomography in recent years, it is now possible to take into account the microscopic details in composite material simulations. However, the composites' complex nature such as inclined and broken fibers, voids, requires rich data to describe these details and thus brings challenging problems in terms of computational time and memory when using traditional simulation methods like the Finite Element Method. These problems become even more severe in simulating failure processes like crack propagation. Hence, it is necessary to investigate more efficient numerical methods for this kind of large scale problems. The MultiGrid (MG) method is such an efficient method, as its computational cost is proportional to the number of unknowns. In this thesis, an efficient MG solver is developed for these problems. The MG method is applied to solve the static elasticity problem based on the Lame's equation and the crack propagation problem based on a phase field method. The accuracy of the MG solutions is validated with Eshelby's classic analytic solution. Then the MG solver is developed to investigate the composite homogenization process and its solutions are compared with existing solutions in the literature. After that, the MG solver is applied to simulate the free-edge effect in laminated composites. A real laminated structure using X-Ray tomography is first simulated. At last, the MG solver is further developed, combined with a phase field method, to simulate the brittle crack propagation. The MG method demonstrates its efficiency both in time and memory dimensions for solving the above problems.

Les modèles dynamiques sont incontournables en synthèse d'animations car ils permettent la simulation réaliste de phénomènes physiques et accordent une meilleure immersion dans un monde virtuel.<br />Plusieurs approches performantes permettent l'animation d'objets déformables, mais les scènes sont souvent complexes à modéliser rendant leur utilisation difficile en pratique.<br />Dans cette thèse nous proposons une solution simplifiant l'animation physique interactive d'objets déformables. Nous suggérons de plonger et d'interpoler l'objet dans une grille déformable sur laquelle s'appliquent des lois mécaniques. Une méthode d'éléments finis rapides et robustes a été étendue afin de prendre en compte la répartition de la matière et plusieurs propriétés de matériaux à l'intérieur d'un élément, et ainsi offrir un comportement amélioré à des résolutions grossières. Afin de concentrer les calculs là où ils sont le plus nécessaires, une formulation multirésolution simple est proposée.<br />Puis nous analysons deux méthodes permettant d'améliorer la propagation des déformations pour des matériaux "mal conditionnés" : une formulation hiérarchique des élément finis, lourde à mettre en place mais permettant facilement la multirésolution, et une formulation multigrid, élégante et performante, mais plus difficile à décliner en multirésolution.<br />Enfin nous validons la précision de notre méthode en la soumettant à diverses expériences.<br />Il en résulte une méthode rapide, robuste, précise et facile d'utilisation aussi bien pour un infographiste, qui peut animer n'importe quel modèle sans connaissances préalables, que pour la modélisation individualisée d'un patient à partir d'images médicales segmentées.

Dans cette thèse, nous proposons des algorithmes et présentons des résultats numériques pour la résolution de jeux répétés stochastiques, à deux joueurs et somme nulle dont l'espace d'état est de grande taille. En particulier, nous considérons la classe de jeux en information complète et en horizon infini. Dans cette classe, nous distinguons d'une part le cas des jeux avec gain actualisé et d'autre part le cas des jeux avec gain moyen. Nos algorithmes, implémentés en C, sont principalement basés sur des algorithmes de type itérations sur les politiques et des méthodes multigrilles. Ces algorithmes sont appliqués soit à des équations de la programmation dynamique provenant de problèmes de jeux à deux joueurs à espace d'états fini, soit à des discrétisations d'équations de type Isaacs associées à des jeux stochastiques différentiels. Dans la première partie de cette thèse, nous proposons un algorithme qui combine l'algorithme des itérations sur les politiques pour les jeux avec gain actualisé à des méthodes de multigrilles algébriques utilisées pour la résolution des systèmes linéaires. Nous présentons des résultats numériques pour des équations d'Isaacs et des inéquations variationnelles. Nous présentons également un algorithme d'itérations sur les politiques avec raffinement de grilles dans le style de la méthode FMG. Des exemples sur des inéquations variationnelles montrent que cet algorithme améliore de façon non négligeable le temps de résolution de ces inéquations. Pour le cas des jeux avec gain moyen, nous proposons un algorithme d'itération sur les politiques pour les jeux à deux joueurs avec espaces d'états et d'actions finis, dans le cas général multichaine (c'est-à-dire sans hypothèse d'irréductibilité sur les chaînes de Markov associées aux stratégies des deux joueurs). Cet algorithme utilise une idée développée dans Cochet-Terrasson et Gaubert (2006). Cet algorithme est basé sur la notion de projecteur spectral non-linéaire d'opérateurs de la programmation dynamique de jeux à un joueur (lequel est monotone et convexe). Nous montrons que la suite des valeurs et valeurs relatives satisfont une propriété de monotonie lexicographique qui implique que l'algorithme termine en temps fini. Nous présentons des résultats numériques pour des jeux discrets provenant d'une variante des jeux de Richman et sur des problèmes de jeux de poursuite. Finalement, nous présentons de nouveaux algorithmes de multigrilles algébriques pour la résolution de systèmes linéaires singuliers particuliers. Ceux-ci apparaissent, par exemple, dans l'algorithme d'itérations sur les politiques pour les jeux stochastiques à deux joueurs et somme nulle avec gain moyen, décrit ci-dessus. Nous introduisons également une nouvelle méthode pour la recherche de mesures invariantes de chaînes de Markov irréductibles basée sur une approche de contrôle stochastique. Nous présentons un algorithme qui combine les itérations sur les politiques d'Howard et des itérations de multigrilles algébriques pour les systèmes linéaires singuliers.

Le but de cette étude est l'analyse de la stabilité et des propriétés de réceptivité de l'écoulement tridimensionnel au bord d'attaque d'une aile en flèche. Le projet est divisé en deux parties: (i) le calcul de l'écoulement de base stationnaire comme une solution de l'état d'équilibre de Navier-Stokes et (ii) l'étude du problème aux valeurs propres direct et adjoint obtenu en linéarisant les équations de Navier-Stokes autour de l'écoulement de base. Un code DNS a été développé sur la base d'un cadre multigrid. La solution des équations de Navier-Stokes non linéaires et stationnaires à différents nombres de Reynolds est obtenue à un coût de calcul de près de O(n), où n est le nombre de degrés de liberté du problème. L'étude de la stabilité et des propriétés de réceptivité est effectuée en résolvant numériquement le problème aux valeurs propres / vecteurs propres. Un algorithme de Krylov-Schur, couplé avec une transformation shift-invert, est utilisé pour extraire la partie la plus intéressante du spectre. Deux branches peuvent être identifiées et l'une d'elles est associée à des vecteurs propres montrant une connexion entre les modes caractéristique du bord d'attaque et les modes de type crossflow. Le wavemaker est localisé dans une région près du bord d'attaque. Les résultats numériques sont comparés qualitativement avec des observations expérimentales et des analyses de stabilité locale.

University of Macau / Faculty of Science and Technology / Department of Mathematics

We propose multigrid methods for solving Hamilton-Jacobi-Bellman (HJB) and Hamilton-Jacobi-Bellman-Isaacs (HJBI) equations. The methods are based on the full approximation scheme. We propose a damped-relaxation method as smoother for multigrid. In contrast with policy iteration, the relaxation scheme is convergent for both HJB and HJBI equations. We show by local Fourier analysis that the damped-relaxation smoother effectively reduces high frequency error. For problems where the control has jumps, restriction and interpolation methods are devised to capture the jump on the coarse grid as well as during coarse grid correction. We will demonstrate the effectiveness of the proposed multigrid methods for solving HJB and HJBI equations arising from option pricing as well as problems where policy iteration does not converge or converges slowly.

Cartesian grids offer a valuable option to simulate aerodynamic flows around complex geometries such as multi-element airfoils, aircrafts, and rockets. Therefore, an adaptively-refined Cartesian grid generator and Euler solver are developed. For the mesh generation part of the algorithm, dynamic data structures are used to determine connectivity information between cells and uniform mesh is created in the domain. Marching squares and cubes algorithms are used to form interfaces of cut and split cells. Geometry-based cell adaptation is applied in the mesh generation. After obtaining appropriate mesh around input geometry, the solution is obtained using either flux vector splitting method or Roe&rsquo / s approximate Riemann solver with cell-centered approach. Least squares reconstruction of flow variables within the cell is used to determine high gradient regions of flow. Solution based adaptation method is then applied to current mesh in order to refine these regions and also coarsened regions where unnecessary small cells exist. Multistage time stepping is used with local time steps to increase the convergence rate. Also FAS multigrid technique is used in order to increase the convergence rate. It is obvious that implementation of geometry and solution based adaptations are easier for Cartesian meshes than other types of meshes. Besides, presented numerical results show the accuracy and efficiency of the algorithm by especially using geometry and solution based adaptation. Finally, Euler solutions of Cartesian grids around airfoils, projectiles and wings are compared with the experimental and numerical data available in the literature and accuracy and efficiency of the solver are verified.