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.

L'objectif de cette thèse est d'examiner comment les technologies orientées-objet peuvent apporter aux applications scientifiques tout ce qu'elles ont apporté dans la programmation des machines séquentielles: une meilleure réutilisabilité et pérennité des codes, des démarches méthodologiques de conception et de réalisation claires... La contrainte du calcul scientifique parallèle de ne pas sacrifier les performances devant être respectée.<br /><br />Après une revue des moyens de programmation parallèle et des<br />concepts objets, la conception et la réalisation d'une bibliothèque parallèle d'algèbre linéaire orientée-objet sont présentées. Nous étudions deux moyens de programmation parallèle, le premier, C++//, est un LAO parallèle à objets actifs dérivé de C++, le second est l'utilisation de MPI au travers d'une surcouche objet minimale.<br />Ces deux approches objets posent des problèmes soit de performances soit de réutilisabilité séquentielle/parallèle qui sont présentés et résolus.<br /><br />Nous proposons notamment un mécanisme simple de partage en lecture pour les modèles à objets actifs, en montrant son utilité en terme de performances de nos applications. Suite à la seconde approche nous définissons les notions de formes de matrices et de matrices avec forme qui permettent d'atteindre nos objectifs de réutilisabilité séquentielle/parallèle.<br /><br />Au final, la conception et la réalisation permettent d'instancier, à partir du même code [séquentiel] d'algèbre linéaire, une version séquentielle et parallèle offrant des performances satisfaisantes.

La première partie est consacrée à la résolution de systèmes linéaires. Le chapitre 1 expose des résultats théoriques et numériques sur les méthodes proposées par Altman et précise le lien avec les méthodes de Krylov. Le chapitre 2 utilise des techniques d'extrapolation introduites par Brezinski pour obtenir une estimation du vecteur erreur. Plusieurs méthodes de projection sont retrouvées et de nouvelles procédures d'accélération données. Dans la deuxième partie, une nouvelle stratégie inspirée de la méthode de Cauchy-Barzilai-Borwein permet de définir de nouveaux schémas résolvant des problèmes de point fixe. Des résultats numériques sur un problème de bifurcation et un théorème de convergence sont donnés. Les chapitres 4, 5 et 6 sont consacrés à l'accélération de l'algorithme EM utilisé pour calculer des estimateurs du maximum de vraisemblance. Une classe de schémas itératifs basés sur la stratégie précédente est présentée, un théorème de convergence et une application à un problème de tomographie sont donnés. La dernière partie, fruit d'un projet du cemracs 2003, traite d'un problème issu de la physique des plasmas : l'amélioration des Codes Particles in Cell à l'aide d'une reconstruction de la densité basée sur une méthode d'ondelettes et sa validation numérique.

.

Dans le présent travail, des nouvelles méthodes de décomposition de domaine et des nouvelles implémentations pour des méthodes existantes sont développées. Une nouvelle méthode basée sur les méthodes antérieures de décomposition du domaine est formulée. Les méthodes classiques FETI plus FETI-2LM sont utilisées pour construire le nouveau Hybrid-FETI. L'idée de base est de développer un nouvel algorithme qui peut utiliser les deux méthodes en même temps en choisissant dans chaque interface l'état le plus adapté en fonction des caractéristiques du problème. En faisant cela, nous recherchons un code plus rapide et plus robuste qui peut fonctionner avec des configurations selon lesquelles les méthodes de base ne le géreront pas de manière optimale par lui-même. La performance est testée sur un problème de contact. La partie suivante implique le développement d'une nouvelle implémentation pour la méthode S-FETI, l'idée est de réduire l'utilisation de la mémoire de cette méthode, afin de pouvoir fonctionner dans des problèmes de taille plus important. Différentes variantes pour cette méthode sont également proposées, tout en cherchant la réduction des directions stockées chaque itération de la méthode itérative. Finalement, une extension de la méthode FETI-2LM à sa version en bloc comme dans S-FETI, est développée. Les résultats numériques pour les différents algorithmes sont présentés. / In this work new domain decomposition methods and new implementations for existing methods are developed. A new method based on previous domain decomposition methods is formulated. The classic FETI plus FETI-2LM methods are used to build the new Hybrid-FETI. The basic idea is to develop a new algorithm that can use both methods at the same time by choosing in each interface the most suited condition depending on the characteristics of the problem. By doing this we search to have a faster and more robust code that can work with configurations that the base methods will not handle it optimally by himself. The performance is tested on a contact problem. The following part involves the development of a new implementation for the S-FETI method, the idea is to reduce the memory usage of this method, to make it able to work in larger problem. Different variation for this method are also proposed, all searching the reduction of directions stored each iteration of the iterative method. Finally, an extension of the FETI-2LM method to his block version as in S-FETI, is developed. Numerical results for the different algorithms are presented.

Nous nous intéressons, dans cette thèse, à l'étude des méthodes d'extrapolation polynômiales et à l'application de ces méthodes dans l'accélération de méthodes de points fixes pour des problèmes donnés. L'avantage de ces méthodes d'extrapolation est qu'elles utilisent uniquement une suite de vecteurs qui n'est pas forcément convergente, ou qui converge très lentement pour créer une nouvelle suite pouvant admettreune convergence quadratique. Le développement de méthodes cycliques permet, deplus, de limiter le coût de calculs et de stockage. Nous appliquons ces méthodes à la résolution des équations de Navier-Stokes stationnaires et incompressibles, à la résolution de la formulation Kohn-Sham de l'équation de Schrödinger et à la résolution d'équations elliptiques utilisant des méthodes multigrilles. Dans tous les cas, l'efficacité des méthodes d'extrapolation a été montrée.Nous montrons que lorsqu'elles sont appliquées à la résolution de systèmes linéaires, les méthodes d'extrapolation sont comparables aux méthodes de sous espaces de Krylov. En particulier, nous montrons l'équivalence entre la méthode MMPE et CMRH. Nous nous intéressons enfin, à la parallélisation de la méthode CMRH sur des processeurs à mémoire distribuée et à la recherche de préconditionneurs efficaces pour cette même méthode.

Nous nous intéressons, dans cette thèse, à l'étude des méthodes d'extrapolation polynômiales et à l'application de ces méthodes dans l'accélération de méthodes de points fixes pour des problèmes donnés. L'avantage de ces méthodes d'extrapolation est qu'elles utilisent uniquement une suite de vecteurs qui n'est pas forcément convergente, ou qui converge très lentement pour créer une nouvelle suite pouvant admettreune convergence quadratique. Le développement de méthodes cycliques permet, deplus, de limiter le coût de calculs et de stockage. Nous appliquons ces méthodes à la résolution des équations de Navier-Stokes stationnaires et incompressibles, à la résolution de la formulation Kohn-Sham de l'équation de Schrödinger et à la résolution d'équations elliptiques utilisant des méthodes multigrilles. Dans tous les cas, l'efficacité des méthodes d'extrapolation a été montrée.Nous montrons que lorsqu'elles sont appliquées à la résolution de systèmes linéaires, les méthodes d'extrapolation sont comparables aux méthodes de sous espaces de Krylov. En particulier, nous montrons l'équivalence entre la méthode MMPE et CMRH. Nous nous intéressons enfin, à la parallélisation de la méthode CMRH sur des processeurs à mémoire distribuée et à la recherche de préconditionneurs efficaces pour cette même méthode. / In this thesis, we study polynomial extrapolation methods. We discuss the design and implementation of these methods for computing solutions of fixed point methods. Extrapolation methods transform the original sequance into another sequence that converges to the same limit faster than the original one without having explicit knowledge of the sequence generator. Restarted methods permit to keep the storage requirement and the average of computational cost low. We apply these methods for computing steady state solutions of incompressible flow problems modelled by the Navier-Stokes equations, for solving the Schrödinger equation using the Kohn-Sham formulation and for solving elliptic equations using multigrid methods. In all cases, vector extrapolation methods have a useful role to play. We show that, when applied to linearly generated vector sequences, extrapolation methods are related to Krylov subspace methods. For example, we show that the MMPE approach is mathematically equivalent to CMRH method. We present an implementation of the CMRH iterative method suitable for parallel architectures with distributed memory. Finally, we present a preconditioned CMRH method.

La résolution de très grands systèmes linéaires creux est une composante de base algorithmique fondamentale dans de nombreuses applications scientifiques en calcul intensif. La résolution per- formante de ces systèmes passe par la conception, le développement et l'utilisation d'algorithmes parallèles performants. Dans nos travaux, nous nous intéressons au développement et l'évaluation d'une méthode hybride (directe/itérative) basée sur des techniques de décomposition de domaine sans recouvrement. La stratégie de développement est axée sur l'utilisation des machines mas- sivement parallèles à plusieurs milliers de processeurs. L'étude systématique de l'extensibilité et l'efficacité parallèle de différents préconditionneurs algébriques est réalisée aussi bien d'un point de vue informatique que numérique. Nous avons comparé leurs performances sur des systèmes de plusieurs millions ou dizaines de millions d'inconnues pour des problèmes réels 3D .