La résolution de problèmes d’onde par une méthode d’éléments finis de frontière (BEM) conduit à des systèmes d’équations linéaires pleins dont la taille augmente très vite pour les applications pratiques. Il est alors impératif d’employer des méthodes de résolution dites rapides. La méthode des multipôles rapides (FMM) accélère la résolution de ces systèmes par des algorithmes itératifs. La méthode des H-matrices permet d’accélérer les solveurs directs nécessaires aux cas d’application massivement multi-seconds membres. Elle a été introduite et théoriquement justifiée dans le cas de l’équation de Laplace.Néanmoins elle s’avère performante au-delà de ce qui est attendu pour des problèmes d’onde relativement haute fréquence. L’objectif de cette thèse est de comprendre pourquoi la méthode fonctionne et proposer des améliorations pour des fréquences plus élevées.Une H-matrice est une représentation hiérarchique par arbre permettant un stockage compressé des données grâce à une séparation des interactions proches (ou singulières)et lointaines (dites admissibles). Un bloc admissible a une représentation de rang faible de type UVT tandis que les interactions singulières sont représentées par des blocs pleins de petites tailles. Cette méthode permet une approximation rapide d’une matrice BEM par une H-matrice ainsi qu’une méthode de factorisation rapide de type Cholesky dont les facteurs sont également de type H-matrice.Nous montrons la nécessité d’un critère d’admissibilité dépendant de la fréquence et introduisons un critère dit de Fresnel basé sur la zone de diffraction de Fresnel. Ceci permet de contrôler la croissance du rang d’un bloc et nous proposons une estimation précise de celui-ci à haute fréquence à partir de résultats sur les fonctions d’onde sphéroïdales.Nous en déduisons une méthode de type HCA-II, robuste et fiable, d’assemblage rapide compressé à la précision voulue.Nous étudions les propriétés de cet algorithme en fonction de divers paramètres et leur influence sur le contrôle et la croissance du rang en fonction de la fréquence.Nous introduisons la notion de section efficace d’interaction entre deux clusters vérifiant le critère de Fresnel. Si celle-ci n’est pas dégénérée, le rang du bloc croît au plus linéairement avec la fréquence ; pour une interaction entre deux clusters coplanaires nous montrons une croissance comme la racine carrée de la fréquence. Ces développements sont illustrés sur des maillages représentatifs des interactions à haute fréquence. / The boundary elements method (BEM) leads to dense linear systemswhose size growsrapidly in pratice ; hence the use of so-called fast methods. The fast multipole method(FMM) accelerates the resolution of BEM systems within an iterative scheme. The H-matrix method speeds up a direct resolution which is needed in massively multiple righthandsides problems. It has been provably introduced in the context of the Laplace equation.However, the use ofH-matrices for relatively high-frequency wave problems leadsto results above expectations. This thesis main goal is to provide an explanation of thesegood results and thus improve the method for higher frequencies.A H-matrix is a compressed tree-based hierarchical representation of the data associated with an admissibility criterion to separate the near (or singular) and far (or compres-sed) fields. An admissible block reads as a UVT rank deficient matrix while the singularblocks are dense with small dimensions. BEM matrices are efficiently represented byH-matrices and this method also allows for a fast Cholesky factorization whose factors arealsoH-matrices.Our work on the admissibility condition emphasizes the necessity of a frequency dependantadmissibility criterion. This new criterion is based on the Fresnel diffraction areathus labelled Fresnel admissibility condition. In that case a precise estimation of the rankof a high-frequency block is proposed thanks to the spheroidal wave functions theory.Consequently, a robust and reliable HCA-II type algorithm has been developed to ensurea compressed precision-controlled assembly. The influence of various parameters on thisnew algorithm behaviour is discussed ; in particular their influence on the control andthe growth of the rank according to the frequency.We define the interaction cross sectionfor two Fresnel-admissible clusters and show in the non-degenerate case that the rankgrowth is linear according to the frequency in the high-frequency regime ; interaction ofcoplanar clusters results in growth like the square root of the frequency. All these resultsare presented on meshes adapted to high-frequency interactions.

Cette étude consiste à résoudre de grands systèmes linéaires creux sur des calculateurs massivement parallèles. Ces systèmes linéaires, souvent rencontrés lors de la simulation numérique de problèmes de mécanique des structures par des codes de calcul par éléments finis, sont résolus avec des coûts très importants en temps de calcul et en espace mémoire. Dans cette thèse, nous mettons au point un parallélisme à deux niveaux et l'intégrons dans les méthodes de décomposition de domaine de type FETI. La démarche s'est organisée autour de trois chapitres principaux. Dans un premier temps, nous mettons en œuvre un solveur direct pour inverser des systèmes linéaires creux qui peuvent être symétriques ou non symétriques, réels ou complexes, à second membre simple ou multiple. La mise en œuvre, basée sur une technique de renumérotation de type dissection emboîtée, est complétée par un point utile dans beaucoup de méthodes de décomposition de domaine (construction d'un préconditionneur ou formulation de l'opérateur de FETI) : la détection de modes à énergie nulle des systèmes singuliers. Dans un deuxième temps, nous parallélisons le solveur direct à travers un modèle de parallélisme à mémoire partagée (multi-threading) pour tirer profit des nouveaux processeurs multi-coeurs. Dans un troisième temps, nous intégrons cette version multi-threads du solveur dans les méthodes FETI pour inverser les problèmes locaux en parallèle. Les résultats de cette étude mettent en évidence l'utilité des travaux effectués et l'intérêt d'utiliser comme solveur local dans les méthodes FETI un solveur direct parallèle robuste et efficace. Tout ceci peut donner accès à de nouvelles gammes de problèmes en calcul des structures. Il serait intéressant de revoir le parallélisme à gros grains entre sous-domaines dans les méthodes FETI. Cela pourrait consister à utiliser la version du solveur direct à second membre multiple pour améliorer plus la méthode itérative utilisée dans la résolution du problème d'interface.

Cette thèse se concentre sur la résolution de systèmes linéaires creux dans le contexte d’applications massivement parallèles. Ce type de problèmes s’exprime sous la forme AX=B, où A est une matrice creuse d’ordre n x n, i.e. qui possède un nombre d’entrées nulles suffisamment élevé pour pouvoir être exploité, et B et X sont respectivement la matrice de seconds membres et la matrice de solution de taille n x nrhs. Cette résolution par des méthodes dites directes est effectuée grâce à une étape de factorisation qui réduit A en deux matrices triangulaires inférieure et supérieure L et U, suivie de deux résolutions triangulaires pour calculer la solution.Nous nous intéressons à ces résolutions avec une attention particulière apportée à la première, LY=B. Dans beaucoup d’applications, B possède un grand nombre de colonnes (nrhs >> 1) transformant la phase de résolution en un goulot d’étranglement. Elle possède souvent aussi une structure creuse, donnant l’opportunité de réduire la complexité de cette étape.Cette étude aborde sous des angles complémentaires la résolution triangulaire de systèmes linéaires avec seconds membres multiples et creux. Nous étudions dans un premier temps la complexité asymptotique de cette étape dans différents contextes (2D, 3D, facteurs compressés ou non). Nous considérons ensuite l’exploitation de cette structure et présentons de nouvelles approches s’appuyant sur une modélisation du problème par des graphes qui permettent d’atteindre efficacement le nombre minimal d’opérations. Enfin, nous donnons une interprétation concrète de son exploitation sur une application d’électromagnétisme pour la géophysique. Nous adaptons aussi des algorithmes parallèles aux spécificités de la phase de résolution.Nous concluons en combinant l'ensemble des résultats précédents et en discutant des perspectives de ce travail. / We consider direct methods to solve sparse linear systems AX = B, where A is a sparse matrix of size n x n with a symmetric structure and X and B are respectively the solution and right-hand side matrices of size n x nrhs. A is usually factorized and decomposed in the form LU, where L and U are respectively a lower and an upper triangular matrix. Then, the solve phase is applied through two triangular resolutions, named respectively the forward and backward substitutions.For some applications, the very large number of right-hand sides (RHS) in B, nrhs >> 1, makes the solve phase the computational bottleneck. However, B is often sparse and its structure exhibits specific characteristics that may be efficiently exploited to reduce this cost. We propose in this thesis to study the impact of the exploitation of this structural sparsity during the solve phase going through its theoretical aspects down to its actual implications on real-life applications.First, we investigate the asymptotic complexity, in the big-O sense, of the forward substitution when exploiting the RHS sparsity in order to assess its efficiency when increasing the problem size. In particular, we study on 2D and 3D regular problems the asymptotic complexity both for traditional full-rank unstructured solvers and for the case when low-rank approximation is exploited. Next, we extend state-of-the-art algorithms on the exploitation of RHS sparsity, and also propose an original approach converging toward the optimal number of operations while preserving performance. Finally, we show the impact of the exploitation of sparsity in a real-life electromagnetism application in geophysics that requires the solution of sparse systems of linear equations with a large number of sparse right-hand sides. We also adapt the parallel algorithms that were designed for the factorization to solve-oriented algorithms.We validate and combine the previous improvements using the parallel solver MUMPS, conclude on the contributions of this thesis and give some perspectives.