京都大学 / 0048 / 新制・課程博士 / 博士(理学) / 甲第18800号 / 理博第4058号 / 新制||理||1584(附属図書館) / 31751 / 京都大学大学院理学研究科地球惑星科学専攻 / (主査)教授 平原 和朗, 教授 澁谷 拓郎, 准教授 久家 慶子 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DGAM

Hierarchical matrix (H-matrix) techniques can be used to efficiently treat dense matrices. With an H-matrix, the storage requirements and performing all fundamental operations, namely matrix-vector multiplication, matrix-matrix multiplication and matrix inversion can be done in almost linear complexity. In this work, we tried to gain even further speedup for the H-matrix arithmetic by utilizing multiple processors. Our approach towards an H-matrix distribution relies on the splitting of the index set. The main results achieved in this work based on the index-wise H-distribution are: A highly scalable algorithm for the H-matrix truncation and matrix-vector multiplication, a scalable algorithm for the H-matrix matrix multiplication, a limited scalable algorithm for the H-matrix inversion for a large number of processors.

Cette étude s’inscrit dans le domaine de la simulation électromagnétique des problèmes de grande taille tels que la diffraction d’ondes planes par de larges plateformes et le rayonnement d’antennes aéroportées. Elle consiste à développer une méthode combinant décomposition en sous-domaines et compression hiérarchique des équations intégrales de frontière. Pour cela, nous rappelons dans un premier temps les points importants de la méthode des équations intégrales de frontière et de leur compression hiérarchique par l’algorithme ACA (Adaptive Cross Approximation). Ensuite, nous présentons la formulation IE-DDM (Integral Equations – Domain Decomposition Method) obtenue à partir d’une représentation intégrale des sous-domaines. Les matrices résultant de la discrétisation de cette formulation sont stockées au format H-matrice (matricehiérarchique). Un solveur spécialement adapté à la résolution de la formulation IE-DDM et à sa représentation hiérarchique a été conçu. Cette étude met en évidence l’efficacité de la décomposition en sous-domaines en tant que préconditionneur des équations intégrales. De plus, la méthode développée est rapide pour la résolution des problèmes à incidences multiples ainsi que la résolution des problèmes basses fréquences / This thesis is about the electromagnetic simulation of large scale problems as the wave scattering from aircrafts and the airborne antennas radiation. It consists in the development of a method combining domain decomposition and hierarchical compression of the surface integral equations. First, we remind the principles of the boundary element method and the hierarchical representation of the surface integral equations with the Adaptive Cross Approximation algorithm. Then, we present the IE-DDM formulation obtained from a sub-domain integral representation. The matrices resulting of the discretization of the formulation are stored in the H-matrix format. A solver especially fitted with the hierarchical representation of the IE-DDM formulation has been developed. This study highlights the efficiency of the sub-domain decomposition as a preconditioner of the integral equations. Moreover, the method is fast for the resolution of multiple incidences and the resolution of low frequencies problems

Il existe une grande quantité de méthodes numériques adaptées d’une part à la modélisation, et d'autre part à la résolution des équations de Maxwell. En particulier, la méthode des éléments nis de frontière (BEM), ou méthode des Moments (MoM), semble appropriée pour la mise en équation des phénomènes de diffraction par des objets parfaitement conducteurs, en limitant le cadre de l'étude à la frontière entre l'objet diffractant et le milieu extérieur. Cette méthode mène systématiquement à la résolution d’un système linéaire dense, que nous parvenons à compresser en l'approchant numériquement par une matrice hiérarchique creuse, appelée H-matrice. Cette approximation peut être complétée d'une ré-agglomération permettant d'améliorer la sparsité de la H-matrice et ainsi d'optimiser davantage la résolution du système traité. La hiérarchisation du système s'effectue en considérant la matrice traitée par blocs, que l'on peut ou non compresser selon une condition d'admissibilité. L'Approximation en Croix Adaptative (ACA) ou l'Approximation en Croix Hybride (HCA) sont deux méthodes de compression que l'on peut alors appliquer aux blocs admissibles. Il existe une grande quantité de méthodes numériques adaptées d’une part à la modélisation, et d'autre part à la résolution des équations de Maxwell. En particulier, la méthode des éléments finis de frontière (BEM), ou méthode des Moments (MoM), semble appropriée pour la mise en équation des phénomènes de diffraction par des objets parfaitement conducteurs, en limitant le cadre de l'étude à la frontière entre l'objet diffractant et le milieu extérieur. Cette méthode mène systématiquement à la résolution d’un système linéaire dense, que nous parvenons à compresser en l'approchant numériquement par une matrice hiérarchique creuse, appelée H-matrice. Cette approximation peut être complétée d'une ré-agglomération permettant d'améliorer la sparsité de la H-matrice et ainsi d'optimiser davantage la résolution du système traité. La hiérarchisation du système s'effectue en considérant la matrice traitée par blocs, que l'on peut ou non compresser selon une condition d'admissibilité. L'Approximation en Croix Adaptative (ACA) ou l'Approximation en Croix Hybride (HCA) sont deux méthodes de compression que l'on peut alors appliquer aux blocs admissibles. Le travail de cette thèse consiste dans un premier temps à valider le format H-matrice en 2D et en 3D en utilisant l'ACA, puis d'y appliquer la méthode HCA, encore peu exploitée. Nous pouvons alors résoudre le système linéaire issu de la BEM en utilisant différents solveurs, directs ou non, adaptés au format hiérarchique. En particulier, nous pourrons constater l'efficacité du préconditionnement LU hiérarchique sur un solveur itératif. Nous pourrons alors appliquer ce formalisme au cas des surfaces rugueuses ou encore des fibres à cristaux photoniques (PCF). Il sera également possible de paralléliser certaines opérations sur architecture partagée afin de réduire de nouveau le coût temporel de la résolution. / A lot of numerical methods are available for the modelization as well as the solution of the Maxwell's equations. In particular the boundary element method (BEM), also known as Method of Moments (MoM), seems appropriate to put in equation the scattering problems by perfectly conducting objects, by restricting the study to the frontier between the diffracting object and its surrounding. This method automatically leads to a dense linear system which we are able to compress, numerically approaching it by a hierarchical sparse matrix, called H-matrix. This approximation can be completed with a coarsening which enhance the sparsity of the H -matrix and thus optimizes again the solution of the concerned system. The hierarchization of the system is done considering the concerned matrix by its blocks, which can or cannot be compressed according to an admissibility condition. The Adaptive Cross Approximation (ACA) or the Hybrid Cross Approximation (HCA) are among the possible compression methods available to compress the admissible blocks. This PhD thesis first focuses on the validation of the H-matrix format both in 2D and 3D using the ACA. We then apply to this format the HCA method, which is still quite unmined. Thus we can solve the linear system coming from the BEM using different direct and iterative solution methods which are adapted to suit the hierarchical format. In particular, we will observe the efficiency of the hierarchical LU preconditionning used to enhance an iterative solver. Thus we will be able to apply this formalism on cases such as rough surfaces or photonic crystal fibers (PCF). It will also be possible to make some operations parallel in order to further reduce the time cost of the solution.

This work addresses the question of the efficient numerical solution of time-domain boundary integral equations with retarded potentials arising in the problems of acoustic and electromagnetic scattering. The convolutional form of the time-domain boundary operators allows to discretize them with the help of Runge-Kutta convolution quadrature. This method combines Laplace-transform and time-stepping approaches and requires the explicit form of the fundamental solution only in the Laplace domain to be known. Recent numerical and analytical studies revealed excellent properties of Runge-Kutta convolution quadrature, e.g. high convergence order, stability, low dissipation and dispersion. As a model problem, we consider the wave scattering in three dimensions. The convolution quadrature discretization of the indirect formulation for the three-dimensional wave equation leads to the lower triangular Toeplitz system of equations. Each entry of this system is a boundary integral operator with a kernel defined by convolution quadrature. In this work we develop an efficient method of almost linear complexity for the solution of this system based on the existing recursive algorithm. The latter requires the construction of many discretizations of the Helmholtz boundary single layer operator for a wide range of complex wavenumbers. This leads to two main problems: the need to construct many dense matrices and to evaluate many singular and near-singular integrals. The first problem is overcome by the use of data-sparse techniques, namely, the high-frequency fast multipole method (HF FMM) and H-matrices. The applicability of both techniques for the discretization of the Helmholtz boundary single-layer operators with complex wavenumbers is analyzed. It is shown that the presence of decay can favorably affect the length of the fast multipole expansions and thus reduce the matrix-vector multiplication times. The performance of H-matrices and the HF FMM is compared for a range of complex wavenumbers, and the strategy to choose between two techniques is suggested. The second problem, namely, the assembly of many singular and nearly-singular integrals, is solved by the use of the Huygens principle. In this work we prove that kernels of the boundary integral operators $w_n^h(d)$ ($h$ is the time step and $t_n=nh$ is the time) exhibit exponential decay outside of the neighborhood of $d=nh$ (this is the consequence of the Huygens principle). The size of the support of these kernels for fixed $h$ increases with $n$ as $n^a,a<1$, where $a$ depends on the order of the Runge-Kutta method and is (typically) smaller for Runge-Kutta methods of higher order. Numerical experiments demonstrate that theoretically predicted values of $a$ are quite close to optimal. In the work it is shown how this property can be used in the recursive algorithm to construct only a few matrices with the near-field, while for the rest of the matrices the far-field only is assembled. The resulting method allows to solve the three-dimensional wave scattering problem with asymptotically almost linear complexity. The efficiency of the approach is confirmed by extensive numerical experiments.

This work addresses the question of the efficient numerical solution of time-domain boundary integral equations with retarded potentials arising in the problems of acoustic and electromagnetic scattering. The convolutional form of the time-domain boundary operators allows to discretize them with the help of Runge-Kutta convolution quadrature. This method combines Laplace-transform and time-stepping approaches and requires the explicit form of the fundamental solution only in the Laplace domain to be known. Recent numerical and analytical studies revealed excellent properties of Runge-Kutta convolution quadrature, e.g. high convergence order, stability, low dissipation and dispersion. As a model problem, we consider the wave scattering in three dimensions. The convolution quadrature discretization of the indirect formulation for the three-dimensional wave equation leads to the lower triangular Toeplitz system of equations. Each entry of this system is a boundary integral operator with a kernel defined by convolution quadrature. In this work we develop an efficient method of almost linear complexity for the solution of this system based on the existing recursive algorithm. The latter requires the construction of many discretizations of the Helmholtz boundary single layer operator for a wide range of complex wavenumbers. This leads to two main problems: the need to construct many dense matrices and to evaluate many singular and near-singular integrals. The first problem is overcome by the use of data-sparse techniques, namely, the high-frequency fast multipole method (HF FMM) and H-matrices. The applicability of both techniques for the discretization of the Helmholtz boundary single-layer operators with complex wavenumbers is analyzed. It is shown that the presence of decay can favorably affect the length of the fast multipole expansions and thus reduce the matrix-vector multiplication times. The performance of H-matrices and the HF FMM is compared for a range of complex wavenumbers, and the strategy to choose between two techniques is suggested. The second problem, namely, the assembly of many singular and nearly-singular integrals, is solved by the use of the Huygens principle. In this work we prove that kernels of the boundary integral operators $w_n^h(d)$ ($h$ is the time step and $t_n=nh$ is the time) exhibit exponential decay outside of the neighborhood of $d=nh$ (this is the consequence of the Huygens principle). The size of the support of these kernels for fixed $h$ increases with $n$ as $n^a,a<1$, where $a$ depends on the order of the Runge-Kutta method and is (typically) smaller for Runge-Kutta methods of higher order. Numerical experiments demonstrate that theoretically predicted values of $a$ are quite close to optimal. In the work it is shown how this property can be used in the recursive algorithm to construct only a few matrices with the near-field, while for the rest of the matrices the far-field only is assembled. The resulting method allows to solve the three-dimensional wave scattering problem with asymptotically almost linear complexity. The efficiency of the approach is confirmed by extensive numerical experiments.