Décrit comme l'un des algorithmes les plus prometteurs du 20ème siècle, le formalisme multipolaire appliqué à la méthode des éléments de frontière, permet de nos jours de traiter de larges problèmes encore inconcevables il y a quelques années. La motivation de ce travail de thèse est d'évaluer la capacité, ainsi que les avantages concernant les ressources numériques, de ce formalisme pour apporter une solution de référence aux problèmes de propagation sonore tri-dimensionnels en environnement urbain, dans l'objectif d'améliorer les algorithmes plus rapides déjà existants. Nous présentons la théorie nécessaire à l'obtention de l'équation intégrale de frontière pour la résolution de problèmes non bornés. Nous discutons également de l'équation intégrale de frontière conventionnelle et hyper-singulière pour traiter les artefacts numériques liés aux fréquences fictives, lorsque l'on résout des problèmes extérieurs. Nous présentons par la suite un bref aperçu historique et technique du formalisme multipolaire rapide et des outils mathématiques requis pour représenter la solution élémentaire de l'équation de Helmholtz. Nous décrivons les principales étapes, d'un point de vue numérique, du calcul multipolaire. Un problème de propagation sonore dans un quartier, composé de 5 bâtiments, nous a permis de mettre en évidence des problèmes d'instabilités dans le calcul par récursion des matrices de translations, se traduisant par des discontinuités sur le champs de pression de surface et une non convergence du solveur. Ceci nous a conduits à considérer le travail très récent de Gumerov et Duraiswamy en lien avec un processus récursif stable pour le calcul des coefficients des matrices de rotation. Cette version améliorée a ensuite été testée avec succès sur un cas de multi diffraction jusqu'à une taille dimensionnelle de problème de 207 longueur d'ondes. Nous effectuons finalement une comparaison entre un algorithme d'élément de frontière, Micado3D, un algorithme multipolaire et un algorithme basé sur le tir de rayons, Icare, pour le calcul de niveaux de pression moyennés dans une cour ouverte et fermée. L'algorithme multipolaire permet de valider les résultats obtenus par tir de rayons dans la cour ouverte jusqu'à 300 Hz (i.e. 100 longueur d'ondes), tandis que concernant la cour fermée, zone très sensible par l'absence de contribution directes ou réfléchies, des études complémentaires sur le préconditionnement de la matrice semblent requises afin de s'assurer de la pertinence des résultats obtenus à l'aide de solveurs itératifs / Described as one of the best ten algorithms of the 20th century, the fast multipole formalism applied to the boundary element method allows to handle large problems which were inconceivable only a few years ago. Thus, the motivation of the present work is to assess the ability, as well as the benefits in term of computational resources provided by the application of this formalism to the boundary element method, for solving sound propagation problems and providing reference solutions, in three dimensional dense urban environments, in the aim of assessing or improving fast engineering tools. We first introduce the mathematical background required for the derivation of the boundary integral equation, for solving sound propagation problems in unbounded domains. We discuss the conventional and hyper-singular boundary integral equation to overcome the numerical artifact of fictitious eigen-frequencies, when solving exterior problems. We then make a brief historical and technical overview of the fast multipole principle and introduce the mathematical tools required to expand the elementary solution of the Helmholtz equation and describe the main steps, from a numerical viewpoint, of fast multipole calculations. A sound propagation problem in a city block made of 5 buildings allows us to highlight instabilities in the recursive computation of translation matrices, resulting in discontinuities of the surface pressure and a no convergence of the iterative solver. This observation leads us to consider the very recent work of Gumerov & Duraiswamy, related to a ``stable'' recursive computation of rotation matrices coefficients in the RCR decomposition. This new improved algorithm has been subsequently assessed successfully on a multi scattering problem up to a dimensionless domain size equal to 207 wavelengths. We finally performed comparisons between a BEM algorithm, extit{Micado3D}, the FMBEM algorithm and a ray tracing algorithm, Icare, for the calculation of averaged pressure levels in an opened and closed court yards. The fast multipole algorithm allowed to validate the results computed with Icare in the opened court yard up to 300 Hz corresponding, (i.e. 100 wavelengths), while in the closed court yard, a very sensitive area without direct or reflective fields, further investigations related to the preconditioning seem required to ensure reliable solutions provided by iterative solver based algorithms

La simulation numérique de la propagation d'ondes sismiques est un besoin actuel, par exemple pour modéliser les vibrations induites dans les sols par le trafic ferroviaire ou pour analyser la propagation d'ondes sismiques ou l'interaction sol-structure. La modélisation de ce type de problèmes est complexe et nécessite l'utilisation de méthodes numériques avancées. La méthode des éléments de frontière (boundary element method, BEM) est une méthode très efficace pour la solution de problèmes de dynamique dans des régions étendues (idéalisées comme non-bornées), en particulier après le développement des méthodes BEM accélérées par multipôle rapide (Fast Multipole Method, FMM), la méthode utilisée dans ce travail de thèse. La BEM est basée sur une formulation intégrale qui nécessite de discrétiser uniquement la frontière du domaine (i.e. une surface en 3-D) et prend implicitement en compte les conditions de radiation à l'infini. En revanche, la BEM nécessite la résolution d'un système linéaire dont la matrice est pleine et (pour la formulation par collocation de la BEM) non-symétrique. Cette méthode est donc trop onéreuse pour des problèmes de grandes dimensions (par exemple O(106) DDLs). L'application à la BEM de la méthode multipôle rapide multi-niveaux (multi-level fast multipole method, ou ML-FMM diminue considérablement la complexité et les besoins de mémoire affectant les formulations BEM classiques, rendant la BEM très compétitive pour modéliser la propagation des ondes élastiques. La version élastodynamique de la ML-FMBEM, dans une forme étendue aux domaines homogènes par morceaux, a par exemple été appliquée avec succès dans un travail précédent (thèse S. Chaillat, ENPC, 2008) pour résoudre les problèmes de propagation des ondes sismiques. Cette thèse vise a développer les capacités de la version élastodynamique fréquentielle de la ML-FMBEM dans deux directions. Premièrement, la formulation de la ML-FMBEM a été étendue au cas de matériaux viscoélastiques linéaires faiblement dissipatifs. Deuxièmement, la ML-FMBEM et la méthode des éléments finis (finite element method, FEM) ont été couplées afin de permettre la résolution de problèmes plus compliqués. En effet, le couplage FEM/FMBEM permet de profiter d'un côté de la flexibilité de la FEM pour la modélisation de structures de géométrie complexe ou présentant des non-linéarités de comportement, de l'autre côté de la prise en compte naturelle par la ML-FMBEM des ondes se propageant dans un milieu étendu et rayonnant à l'infini. De nouvelles perspectives d'application (par exemple prise en compte d'hétérogénéités, non-linéarités de comportement) sont ainsi ouvertes. Dans cette thèse, nous avons considéré deux stratégies pour coupler la FMBEM et la FEM avec l'objectif de résoudre les problèmes tridimensionnels de propagation des ondes harmoniques dans le temps et dans des domaines non-bornés. L'idée principale consiste à séparer une ou plusieurs sous-régions pouvant contenir des structures complexes, de fortes hétérogénéités ou des non-linéarités (modélisées au moyen de la FEM) du milieu propagatif complémentaire semi-infini et (visco-) élastique (modélisé au moyen de la FMBEM). Cette séparation est effectuée au moyen d'une décomposition de domaines sans recouvrement. Le deux approches proposées ont été mises en oeuvre, et une série d'expérimentations numériques a été effectuée pour les évaluer et les comparer / The numerical simulation of elastic wave propagation in unbounded media is a topical issue. This need arises in a variety of real life engineering problems, from the modelling of railway- or machinery-induced vibrations to the analysis of seismic wave propagation and soil-structure interaction problems. Due to the complexity of the involved geometries and materials behavior, modelling such situations requires sophisticated numerical methods. The Boundary Element method (BEM) is a very effective approach for dynamical problems in spatially-extended regions (idealized as unbounded), especially since the advent of fast BEMs such as the Fast Multipole Method (FMM) used in this work. The BEM is based on a boundary integral formulation which requires the discretization of the only domain boundary (i.e. a surface in 3-D) and accounts implicitly for the radiation conditions at infinity. As a main disadvantage, the BEM leads a priori to a fully-populated and (using the collocation approach) non-symmetrical coefficient matrix, which make the traditional implementation of this method prohibitive for large problems (say O(106) boundary DoFs). Applied to the BEM, the Multi-Level Fast Multipole Method (ML-FMM) strongly lowers the complexity in computational work and memory that hinder the classical formulation, making the ML-FMBEM very competitive in modelling elastic wave propagation. The elastodynamic version of the Fast Multipole BEM (FMBEM), in a form enabling piecewise-homogeneous media, has for instance been successfully used to solve seismic wave propagation problems in a previous work (thesis dissertation of S. Chaillat, ENPC, 2008). This thesis aims at extending the capabilities of the existing frequency-domain elastodynamic FMBEM in two directions. Firstly, the time-harmonic elastodynamic ML-FMBEM formulation has been extended to the case of weakly dissipative viscoelastic media. Secondly, the FMBEM and the Finite Element Method (FEM) have been coupled to take advantage of the versatility of the FEM to model complex geometries and non-linearities while the FM-BEM accounts for wave propagation in the surrounding unbounded medium. In this thesis, we consider two strategies for coupling the FMBEM and the FEM to solve three-dimensional time-harmonic wave propagation problems in unbounded domains. The main idea is to separate one or more bounded subdomains (modelled by the FEM) from the complementary semi-infinite viscoelastic propagation medium (modelled by the FMBEM) through a non-overlapping domain decomposition. Two coupling strategies have been implemented and their performances assessed and compared on several examples

Das wissenschaftliche Rechnen mit der Computersimulation hat sich heute als dritte Säule der wissenschaftlichen Methodenlehre neben der Theorie und dem Experiment etabliert. Aufgabe der Informatik im wissenschaftlichen Rechnen ist es, sowohl effiziente Simulationsalgorithmen zu entwickeln als auch ihre effiziente Implementierung. Die vorliegende Arbeit richtet ihren Fokus auf die effiziente Implementierung zweier wichtiger Verfahren des wissenschaftlichen Rechnens: die Schnelle Multipolmethode (FMM) für Teilchensimulationen und die Methode der finiten Elemente (FEM), die z. B. zur Berechnung der Deformation von Festkörpern genutzt wird. Die Effizienz der Implementierung bezieht sich hier auf die Ausführungszeit der Simulationen und den zur Ausführung notwendigen Energieverbrauch der eingesetzten Rechnersysteme. Die Steigerung der Effizienz wurde durch modellbasiertes Autotuning erreicht. Beim modellbasierten Autotuning wird für die wesentlichen Teile des Algorithmus ein Modell aufgestellt, das dessen Ausführungszeit bzw. Energieverbrauch beschreibt. Dieses Modell ist abhängig von Eigenschaften des genutzten Rechnersystems, von Eingabedaten und von verschiedenen Parametern des Algorithmus. Die Eigenschaften des Rechnersystems werden durch Ausführung des tatsächlich genutzten Codes für verschiedene Implementierungsvarianten ermittelt. Diese umfassen eine CPU-Implementierung und eine Grafikprozessoren-Implementierung für die FEM und die Implementierung der Nahfeld- und der Fernfeldwechselwirkungsberechnung für die FMM. Anhand der aufgestellten Modelle werden die Kosten der Ausführung für jede Variante vorhergesagt. Die optimalen Algorithmenparameter können somit analytisch bestimmt werden, um die gewünschte Zielgröße, also Ausführungszeit oder Energieverbrauch, zu minimieren. Bei der Ausführung der Simulation werden die effizientesten Implementierungsvarianten entsprechend der Vorhersage genutzt. Während bei der FMM die Performance-Messungen unabhängig von der Ausführung der Simulation durchgeführt werden, wird für die FEM ein Verfahren zur dynamischen Verteilung der Rechenlast zwischen CPU und GPU vorgestellt, das auf Ausführungszeitmessungen zur Laufzeit der Simulation reagiert. Durch Messung der tatsächlichen Ausführungszeiten kann so dynamisch auf sich während der Laufzeit verändernde Verhältnisse reagiert und die Verteilung der Rechenlast entsprechend angepasst werden. Die Ergebnisse dieser Arbeit zeigen, dass modellbasiertes Autotuning es ermöglicht, die Effizienz von Anwendungen des wissenschaftlichen Rechnens in Bezug auf Ausführungszeit und Energieverbrauch zu steigern. Insbesondere die Berücksichtigung des Energieverbrauchs alternativer Ausführungspfade, also die Energieadaptivität, wird in naher Zukunft von großer Bedeutung im wissenschaftlichen Rechnen sein. / Computer simulation as a part of the scientific computing has established as third pillar in scientific methodology, besides theory and experiment. The task of computer science in the field of scientific computing is the development of efficient simulation algorithms as well as their efficient implementation. The thesis focuses on the efficient implementation of two important methods in scientific computing: the Fast Multipole Method (FMM) for particle simulations, and the Finite Element Method (FEM), which is, e.g., used for deformation problems of solids. The efficiency of the implementation considers the execution time of the simulations and the energy consumption of the computing systems needed for the execution. The method used for increasing the efficiency is model-based autotuning. For model-based autotuning, a model for the substantial parts of the algorithm is set up which estimates the execution time or energy consumption. This model depends on properties of the computer used, of the input data and of parameters of the algorithm. The properties of the computer are determined by executing the real code for different implementation variants. These implementation variantss comprise a CPU and a graphics processor implementation for the FEM, and implementations of near field and far field interaction calculations for the FMM. Using the models, the execution costs for each variant are predicted. Thus, the optimal algorithm parameters can be determined analytically for a minimisation of the desired target value, i.e. execution time or energy consumption. When the simulation is executed, the most efficient implementation variants are used depending on the prediction of the model. While for the FMM the performance measurement takes place independently from the execution of the simulation, for the FEM a method for dynamically distributing the workload to the CPU and the GPU is presented, which takes into account execution times measured at runtime. By measuring the real execution times, it is possible to response to changing conditions and to adapt the distribution of the workload accordingly. The results of the thesis show that model-based autotuning makes it possible to increase the efficiency of applications in scientific computing regarding execution time and energy consumption. Especially, the consideration of the energy consumption of alternative execution paths, i.e. the energy adaptivity, will be of great importance in scientific computing in the near future.

Das wissenschaftliche Rechnen mit der Computersimulation hat sich heute als dritte Säule der wissenschaftlichen Methodenlehre neben der Theorie und dem Experiment etabliert. Aufgabe der Informatik im wissenschaftlichen Rechnen ist es, sowohl effiziente Simulationsalgorithmen zu entwickeln als auch ihre effiziente Implementierung. Die vorliegende Arbeit richtet ihren Fokus auf die effiziente Implementierung zweier wichtiger Verfahren des wissenschaftlichen Rechnens: die Schnelle Multipolmethode (FMM) für Teilchensimulationen und die Methode der finiten Elemente (FEM), die z. B. zur Berechnung der Deformation von Festkörpern genutzt wird. Die Effizienz der Implementierung bezieht sich hier auf die Ausführungszeit der Simulationen und den zur Ausführung notwendigen Energieverbrauch der eingesetzten Rechnersysteme. Die Steigerung der Effizienz wurde durch modellbasiertes Autotuning erreicht. Beim modellbasierten Autotuning wird für die wesentlichen Teile des Algorithmus ein Modell aufgestellt, das dessen Ausführungszeit bzw. Energieverbrauch beschreibt. Dieses Modell ist abhängig von Eigenschaften des genutzten Rechnersystems, von Eingabedaten und von verschiedenen Parametern des Algorithmus. Die Eigenschaften des Rechnersystems werden durch Ausführung des tatsächlich genutzten Codes für verschiedene Implementierungsvarianten ermittelt. Diese umfassen eine CPU-Implementierung und eine Grafikprozessoren-Implementierung für die FEM und die Implementierung der Nahfeld- und der Fernfeldwechselwirkungsberechnung für die FMM. Anhand der aufgestellten Modelle werden die Kosten der Ausführung für jede Variante vorhergesagt. Die optimalen Algorithmenparameter können somit analytisch bestimmt werden, um die gewünschte Zielgröße, also Ausführungszeit oder Energieverbrauch, zu minimieren. Bei der Ausführung der Simulation werden die effizientesten Implementierungsvarianten entsprechend der Vorhersage genutzt. Während bei der FMM die Performance-Messungen unabhängig von der Ausführung der Simulation durchgeführt werden, wird für die FEM ein Verfahren zur dynamischen Verteilung der Rechenlast zwischen CPU und GPU vorgestellt, das auf Ausführungszeitmessungen zur Laufzeit der Simulation reagiert. Durch Messung der tatsächlichen Ausführungszeiten kann so dynamisch auf sich während der Laufzeit verändernde Verhältnisse reagiert und die Verteilung der Rechenlast entsprechend angepasst werden. Die Ergebnisse dieser Arbeit zeigen, dass modellbasiertes Autotuning es ermöglicht, die Effizienz von Anwendungen des wissenschaftlichen Rechnens in Bezug auf Ausführungszeit und Energieverbrauch zu steigern. Insbesondere die Berücksichtigung des Energieverbrauchs alternativer Ausführungspfade, also die Energieadaptivität, wird in naher Zukunft von großer Bedeutung im wissenschaftlichen Rechnen sein. / Computer simulation as a part of the scientific computing has established as third pillar in scientific methodology, besides theory and experiment. The task of computer science in the field of scientific computing is the development of efficient simulation algorithms as well as their efficient implementation. The thesis focuses on the efficient implementation of two important methods in scientific computing: the Fast Multipole Method (FMM) for particle simulations, and the Finite Element Method (FEM), which is, e.g., used for deformation problems of solids. The efficiency of the implementation considers the execution time of the simulations and the energy consumption of the computing systems needed for the execution. The method used for increasing the efficiency is model-based autotuning. For model-based autotuning, a model for the substantial parts of the algorithm is set up which estimates the execution time or energy consumption. This model depends on properties of the computer used, of the input data and of parameters of the algorithm. The properties of the computer are determined by executing the real code for different implementation variants. These implementation variantss comprise a CPU and a graphics processor implementation for the FEM, and implementations of near field and far field interaction calculations for the FMM. Using the models, the execution costs for each variant are predicted. Thus, the optimal algorithm parameters can be determined analytically for a minimisation of the desired target value, i.e. execution time or energy consumption. When the simulation is executed, the most efficient implementation variants are used depending on the prediction of the model. While for the FMM the performance measurement takes place independently from the execution of the simulation, for the FEM a method for dynamically distributing the workload to the CPU and the GPU is presented, which takes into account execution times measured at runtime. By measuring the real execution times, it is possible to response to changing conditions and to adapt the distribution of the workload accordingly. The results of the thesis show that model-based autotuning makes it possible to increase the efficiency of applications in scientific computing regarding execution time and energy consumption. Especially, the consideration of the energy consumption of alternative execution paths, i.e. the energy adaptivity, will be of great importance in scientific computing in the near future.