The Fast Multipole Method (FMM) allows for rapid evaluation of the fundamental solution of the Helmholtz equation, known as Green's function. Evaluation times are reduced from O(N^2), using the direct approach, down to O(N log N), with an accuracy specified by the user. The Helmholtz equation, and variations thereof, including the Laplace and wave equations, are used to describe physical phenomena in electromagnetics, acoustics, heat dissipation, and many other applications. This thesis studies the acceleration of the low-frequency FMM, where the product of the wave number and the translation distance of expansion coefficients is relatively low. A general-purpose graphics processing unit (GPGPU), with native support of double-precision arithmetic, was used in the implementation of the LF FMM, with a resulting speedup of 4-22X over a conventional central processing unit (CPU), running in a single-threaded manner, for various simulations involving hundreds of thousands to millions of sources.

The Fast Multipole Method (FMM) allows for rapid evaluation of the fundamental solution of the Helmholtz equation, known as Green's function. Evaluation times are reduced from O(N^2), using the direct approach, down to O(N log N), with an accuracy specified by the user. The Helmholtz equation, and variations thereof, including the Laplace and wave equations, are used to describe physical phenomena in electromagnetics, acoustics, heat dissipation, and many other applications. This thesis studies the acceleration of the low-frequency FMM, where the product of the wave number and the translation distance of expansion coefficients is relatively low. A general-purpose graphics processing unit (GPGPU), with native support of double-precision arithmetic, was used in the implementation of the LF FMM, with a resulting speedup of 4-22X over a conventional central processing unit (CPU), running in a single-threaded manner, for various simulations involving hundreds of thousands to millions of sources.

Le sujet de cette thèse traite de l'amélioration de la méthode PEEC inductive (permettant une modélisation des interconnexions électriques d'un point de vue électromagnétique basse fréquence) en employant une méthode de compression matricielle FMM. L'introduction de ces compressions entraîne des restrictions concernant les opérations algébriques autorisées, seule les opérations de type produit matrice - vecteur sont permises. L'objectif était de proposer des méthodes pour déterminer : Les courants en tout point du dispositif Des impédances équivalentes entre différents ports d'entrées-sorties. Le premier point a pu être traité en mettant en place une méthode originale de recherche d'un jeu d'équations indépendantes ainsi qu'un préconditionneur spécifique dans la phase de résolution compatible avec les méthodes de compression matricielle. Le second point a nécessité l'utilisation de méthode de réduction d'ordre à base de sous espace de Krylov afin de construire un développement limité des jeux d'impédance recherché. Ensuite, nous avons mis en place une technique de synthèse de circuit afin d'obtenir un circuit électrique simple permettant de modéliser le comportement du dispositif avec de simples éléments de type résistance, inductance (non couplée) et capacité. Cette démarche permet l'utilisation dans tous les simulateurs temporels et ainsi permet d'avoir une vision système légère du dispositif d'interconnexion électrique. / This thesis deals with the improvement of the inductive PEEC method (for modelling electrical interconnections of low frequency) using the matrix compression Fast Multipole Method (FMM). The introduction of FMM leads to only algebraic operation of type matrix - vector product is permitted. The objective of this thesis was to propose some methods to determine: • Currents at any point of the device • The equivalent impedances between different input-output ports. The first point has been treated by introducing a novel method to determine a set of independent equations. The choice of iterative methods in solving linear system imposed on the establishment of a specific preconditioner compatible with matrix compression methods. The second point require to describe the Kirchoff law in the form of state space equation and to use model order reduction method based on Krylov subspace to compute Taylor series of impedance matrix. Once again, all the steps are necessary to be taked into account the use of matrix compression method FMM. Following our order reduction method, we implemented a circuit synthesis technique to obtain a simple electrical circuit which conserve the behavior of the device by simple elements like resistance, inductance (uncoupled) and capacity. This approach allows the reuse of reduction model in all time domain simulation software. For global system, it provides also a light model of electrical interconnection device.

La modélisation numérique de la multi-fissuration et son influence sur les ouvrages du Génie Civil reste un sujet ouvert et nécessite le développement de nouveaux outils numériques de plus en plus performants. L’approche retenue dans cette thèse est basée sur l’utilisation des concepts des équations intégrales de Galerkin accélérées par la méthode multipôle rapide. Les méthodes intégrales sont bien connues pour leur souplesse à définir des géométries complexes en 3D. Elles restent également très performantes en mécanique de la rupture, lors de la détermination des champs singuliers au voisinage des fissures. La Méthode Multipôle Rapide, quant à elle, permet via une judicieuse reformulation des fonctions fondamentales propres aux formulations intégrales, de réduire considérablement le coût des calculs. La mise en œuvre de la FM-SGBEM a permis de pallier les difficultés rencontrées lors de la phase de résolution et ce lorsqu’on traite de domaines de grandes tailles par équations intégrales de Galerkin pures. Les présents travaux, viennent en partie optimiser et renforcer cette phase dans les environnements numériques existants. D’autre part, des adaptations et des développements théoriques des formulations FM-SGBEM pour prendre en compte le caractère hétérogène des domaines en Génie Civil qui en découlent, ont fait l’objet d’une large partie des travaux développés dans cette thèse. La modélisation du phénomène de propagation de fissures par fatigue a également été étudiée avec succès. Enfin, une application sur une structure de chaussée souple a permis de valider les modèles ainsi développés en propagation de fissures par fatigue dans des structures hétérogènes. De réelles perspectives d’optimisations et de développements de cet outil numérique restent envisagées. / The modeling of cracks and its influence on the understanding of the behaviors of the civil engineering structures is an open topic since many decades. To take into consideration complex configurations, it is necessary to construct more robust and more efficient algorithms. In this work, the approach Galerkin of the boundary integral equations (Symmetric Galerkin Boundary Element Method) coupled with the Fast Multipole Method (FMM) has been adopted. The boundary analysis are well-known for the flexibility to treat sophisticated geometries (unbounded/semi-unbounded) whilst reducing the problem dimension or for the good accuracy when dealing with the singularities. By coupling with the FMM, all the bottle-necks of the traditional BEM due to the fully-populated matrices or the slow evaluations of the integrals have been reduced, thus making the FM-SGBEM an attractive alternative for problems in fracture mechanics. In this work, the existing single-region formulations have been extended to multi-region configurations along with several types of solicitations. Many efforts have also been spent to improve the efficiency of the numerical algorithms. Fatigue crack propagations have been implemented and some practical simulations have been considered. The obtained results have validated the numerical program and have also opened many perspectives of further developments for the code.

<p>In this report we describe simulation of the surface current density on a PEC cylinder and the diffracted field for a line source above a finite PEC ground plane as a means to verify the Nero2D program. The results are compared with the exact solution and give acceptable errors. A terrain model for a communication link is studied in the report and we simulate the wave propagation for terrain with irregular shapes and different materials. The Nero2D program is based on the fast multipole method (FMM) to reduce computation time and memory. Gaussian sources are also studied to make the terrain model more realistic</p>

Le sujet de cette thèse traite de l'amélioration de la méthode PEEC inductive (permettant une modélisation des interconnexions électriques d'un point de vue électromagnétique basse fréquence) en employant une méthode de compression matricielle FMM. L'introduction de ces compressions entraîne des restrictions concernant les opérations algébriques autorisées, seule les opérations de type produit matrice - vecteur sont permises. L'objectif était de proposer des méthodes pour déterminer : Les courants en tout point du dispositif Des impédances équivalentes entre différents ports d'entrées-sorties. Le premier point a pu être traité en mettant en place une méthode originale de recherche d'un jeu d'équations indépendantes ainsi qu'un préconditionneur spécifique dans la phase de résolution compatible avec les méthodes de compression matricielle. Le second point a nécessité l'utilisation de méthode de réduction d'ordre à base de sous espace de Krylov afin de construire un développement limité des jeux d'impédance recherché. Ensuite, nous avons mis en place une technique de synthèse de circuit afin d'obtenir un circuit électrique simple permettant de modéliser le comportement du dispositif avec de simples éléments de type résistance, inductance (non couplée) et capacité. Cette démarche permet l'utilisation dans tous les simulateurs temporels et ainsi permet d'avoir une vision système légère du dispositif d'interconnexion électrique.

Le sujet de cette thèse traite de l'amélioration de la méthode PEEC inductive (permettant une modélisation des interconnexions électriques d'un point de vue électromagnétique basse fréquence) en employant une méthode de compression matricielle FMM. L'introduction de ces compressions entraîne des restrictions concernant les opérations algébriques autorisées, seule les opérations de type produit matrice - vecteur sont permises. L'objectif était de proposer des méthodes pour déterminer : * Les courants en tout point du dispositif * Des impédances équivalentes entre différents ports d'entrées-sorties. Le premier point a pu être traité en mettant en place une méthode originale de recherche d'un jeu d'équations indépendantes ainsi qu'un préconditionneur spécifique dans la phase de résolution compatible avec les méthodes de compression matricielle. Le second point a nécessité l'utilisation de méthode de réduction d'ordre à base de sous espace de Krylov afin de construire un développement limité des jeux d'impédance recherché. Ensuite, nous avons mis en place une technique de synthèse de circuit afin d'obtenir un circuit électrique simple permettant de modéliser le comportement du dispositif avec de simples éléments de type résistance, inductance (non couplée) et capacité. Cette démarche permet l'utilisation dans tous les simulateurs temporels et ainsi permet d'avoir une vision système légère du dispositif d'interconnexion électrique

In this report we describe simulation of the surface current density on a PEC cylinder and the diffracted field for a line source above a finite PEC ground plane as a means to verify the Nero2D program. The results are compared with the exact solution and give acceptable errors. A terrain model for a communication link is studied in the report and we simulate the wave propagation for terrain with irregular shapes and different materials. The Nero2D program is based on the fast multipole method (FMM) to reduce computation time and memory. Gaussian sources are also studied to make the terrain model more realistic

The current trends in computer architecture are shifting towards smaller byte/flop ratios, while available parallelism is increasing at all levels of granularity – vector length, core count, and MPI process. Intel’s Xeon Phi coprocessor, NVIDIA’s Kepler GPU, and IBM’s BlueGene/Q all have a Byte/flop ratio close to 0.2, which makes it very difficult for most algorithms to extract a high percentage of the theoretical peak flop/s from these architectures. Popular algorithms in scientific computing such as FFT are continuously evolving to keep up with this trend in hardware. In the meantime it is also necessary to invest in novel algorithms that are more suitable for computer architectures of the future. The fast multipole method (FMM) was originally developed as a fast algorithm for ap- proximating the N-body interactions that appear in astrophysics, molecular dynamics, and vortex based fluid dynamics simulations. The FMM possesses have a unique combination of being an efficient O(N) algorithm, while having an operational intensity that is higher than a matrix-matrix multiplication. In fact, the FMM can reduce the requirement of Byte/flop to around 0.01, which means that it will remain compute bound until 2020 even if the cur- rent trend in microprocessors continues. Despite these advantages, there have not been any benchmarks of FMM codes on modern architectures such as Xeon Phi, Kepler, and Blue- Gene/Q. This study aims to provide a comprehensive benchmark of a state of the art FMM code “exaFMM” on the latest architectures, in hopes of providing a useful reference for deciding when the FMM will become useful as the computational engine in a given application code. It may also serve as a warning to certain problem size domains areas where the FMM will exhibit insignificant performance improvements. Such issues depend strongly on the asymptotic constants rather than the asymptotics themselves, and therefore are strongly implementation and hardware dependent. The primary objective of this study is to provide these constants on various computer architectures.

One of the biggest challenges facing geoscientists is the ability to accurately predict failure within a rock mass. Conventionally, numerical modeling is performed to predict the response of the rock mass due to excavation. However, numerical modeling relies heavily on the estimated physical characteristics of the rock mass. Unless dense, costly sampling of the rock mass has been performed, the results of the modeling are not robust. Seismic tomography offers a unique advantage of monitoring the rock mass response over conventional numerical modeling because it is able to measure the true alteration in response to excavation (Westman, 2003). This paper utilizes a tomographic inversion scheme using the Fast Marching Method for raypath tracing and the Simultaneous Iterative Reconstruction Technique to solve the p-wave velocity model of an underground mine and surrounding rock mass. The inversion scheme presented is tested using a data set from Creighton Mine in Sudbury, Ontario, Canada and includes 9,270 distinct events over 62 days. A total of 53 geophones recorded 191,856 p-waves that are able to be used for inversion. Temporal monitoring of the seismic p-wave velocity in the vicinity of a known Mw 2.6 fault-slip event that occurred on March 14th is performed by creating tomograms of the axial plane at the depth of the event and of an oblique plane where a dense distribution of events occurred including the March 14th event. Tomograms are produced on a weekly basis leading up to the event and also on a daily basis three days before the event. The weekly tomograms reveal a decrease in p-wave velocity in the vicinity of the Mw 2.6 event as time approaches the event and then a significant increase 1,600 ft/sec larger than the background velocity the week of the event. The daily tomograms reveal a 1,200 ft/sec velocity increase in the same area from March 13th to March 14th, however, no trends in the daily or weekly tomograms prior to the date of the March 14th event suggest the known event is imminent. / Master of Science