Les équations de Maxwell en régime harmonique comportent plusieurs difficultés lorsque la fréquence est élevée. On peut notamment citer le fait que leur formulation variationnelle n’est pas définie positive et l’effet de pollution qui oblige à utiliser des maillages très fins, ce qui rend problématique la construction de solveurs itératifs. Nous proposons une stratégie de solution précise et rapide, qui associe une discrétisation par des éléments finis d’ordre élevé à des préconditionneurs de type décomposition de domaine. La conception, l’implémentation et l’analyse des deux méthodes sont assez difficiles pour les équations de Maxwell. Les éléments finis adaptés à l’approximation du champ électrique sont les éléments finis H(rot)-conformes ou d’arête. Ici nous revisitons les degrés de liberté classiques définis par Nédélec, afin d’obtenir une expression plus pratique par rapport aux fonctions de base d’ordre élevé choisies. De plus, nous proposons une technique pour restaurer la dualité entre les fonctions de base et les degrés de liberté. Nous décrivons explicitement une stratégie d’implémentation qui a été appliquée dans le langage open source FreeFem++. Ensuite, nous nous concentrons sur les techniques de préconditionnement du système linéaire résultant de la discrétisation par éléments finis. Nous commençons par la validation numérique d’un préconditionneur à un niveau, de type Schwarz avec recouvrement, avec des conditions de transmission d’impédance entre les sous-domaines. Enfin, nous étudions comment des préconditionneurs à deux niveaux, analysés récemment pour l’équation de Helmholtz, se comportent pour les équations de Maxwell, des points de vue théorique et numérique. Nous appliquons ces méthodes à un problème à grande échelle qui découle de la modélisation d’un système d’imagerie micro-onde, pour la détection et le suivi des accidents vasculaires cérébraux. La précision et la vitesse de calcul sont essentielles dans cette application. / The time-harmonic Maxwell’s equations present several difficulties when the frequency is large, such as the sign-indefiniteness of the variational formulation, the pollution effect and the problematic construction of iterative solvers. We propose a precise and efficient solution strategy that couples high order finite element (FE) discretizations with domain decomposition (DD) preconditioners. High order FE methods make it possible for a given precision to reduce significantly the number of unknowns of the linear system to be solved. DD methods are then used as preconditioners for the iterative solver: the problem defined on the global domain is decomposed into smaller problems on subdomains, which can be solved concurrently and using robust direct solvers. The design, implementation and analysis of both these methods are particularly challenging for Maxwell’s equations. FEs suited for the approximation of the electric field are the curl-conforming or edge finite elements. Here, we revisit the classical degrees of freedom (dofs) defined by Nédélec to obtain a new more friendly expression in terms of the chosen high order basis functions. Moreover, we propose a general technique to restore duality between dofs and basis functions. We explicitly describe an implementation strategy, which we embedded in the open source language FreeFem++. Then we focus on the preconditioning of the linear system, starting with a numerical validation of a one-level overlapping Schwarz preconditioner, with impedance transmission conditions between subdomains. Finally, we investigate how two-level preconditioners recently analyzed for the Helmholtz equation work in the Maxwell case, both from the theoretical and numerical points of view. We apply these methods to the large scale problem arising from the modeling of a microwave imaging system, for the detection and monitoring of brain strokes. In this application accuracy and computing speed are indeed of paramount importance.

High-frequency wave phenomena is observed in many physical settings, most notably in acoustics, electromagnetics, and elasticity. In all of these fields, numerical simulation and modeling of the forward propagation problem is important to the design and analysis of many systems; a few examples which rely on these computations are the development of metamaterial technologies and geophysical prospecting for natural resources. There are two modes of modeling the forward problem: the frequency domain and the time domain. As the title states, this work is concerned with the former regime. The difficulties of solving the high-frequency wave propagation problem accurately lies in the large number of degrees of freedom required. Conventional wisdom in the computational electromagnetics commmunity suggests that about 10 degrees of freedom per wavelength be used in each coordinate direction to resolve each oscillation. If K is the width of the domain in wavelengths, the number of unknowns N grows at least by O(K^2) for surface discretizations and O(K^3) for volume discretizations in 3D. The memory requirements and asymptotic complexity estimates of direct algorithms such as the multifrontal method are too costly for such problems. Thus, iterative solvers must be used. In this dissertation, I will present fast algorithms which, in conjunction with GMRES, allow the solution of the forward problem in O(N) or O(N log N) time. / text

Στη παρούσα διπλωματική εργασία ασχολούμαστε με την αποδοτική επίλυση ταινιακών και γενικών, αραιών γραμμικών συστημάτων σε παράλληλες αρχιτεκτονικές μέσω της οικογένειας αλγορίθμων Spike. Ζητούμενο είναι η βελτίωση (μείωση) του χρόνου επίλυσης μέσω τεχνικών επίλυσης γραμμικών συστημάτων με πολλά δεξιά μέλη. Πιο συγκεκριμένα, επικεντρωνόμαστε στην επίλυση της εξίσωσης μητρώου $AX=F$ (1) όπου $A\in \mathbb{R}^{n\times n}$ είναι το μητρώο συντελεστών και το οποίο είναι αραιό ή/και ταινιακό, $F\in \mathbb{R}^{n\times s}$ είναι ένα μητρώο με $s$ στήλες το οποίο ονομάζεται μητρώο δεξιών μελών και $X\in \mathbb{R}^{n\times s}$ είναι η λύση του συστήματος. Μια σημαντική μέθοδος για την παράλληλη επίλυση της παραπάνω εξίσωσης, είναι η μέθοδος Spike και οι παραλλαγές της. Η μέθοδος Spike βασίζεται στη τεχνική διαίρει και βασίλευε και αποτελείται από δυο φάσεις: α) επίλυση ανεξάρτητων υπο-προβλημάτων τοπικά σε κάθε επεξεργαστή, και β) επίλυση ενός πολύ μικρότερου προβλήματος το οποίο απαιτεί επικοινωνία μεταξύ των επεξεργαστών. Οι δύο φάσεις συνδυάζονται ώστε να παραχθεί η τελική λύση $X$. Η συνεισφορά της διπλωματικής εργασίας έγκειται στην επιτάχυνση της οικογένειας αλγορίθμων Spike για την επίλυση της εξίσωσης (1) μέσω της μελέτης, το σχεδιασμό και την υλοποίηση νέων, περισσότερο αποδοτικών αλγοριθμικών σχημάτων τα οποία βασίζονται σε τεχνικές επίλυσης γραμμικών συστημάτων με πολλά δεξιά μέλη. Αυτά τα νέα αλγοριθμικά σχήματα έχουν ως στόχο τη βελτίωση του χρόνου επίλυσης των γραμμικών συστημάτων καθώς και άλλα οφέλη όπως η αποδοτικότερη χρήση μνήμης. / In this thesis we focus on the efficient solution of general banded and general sparse linear systems on parallel architectures by exploiting the Spike family of algorithms. The equation of interest can be written in matrix form as $ AX = F $ (1) where $ A \ in \ mathbb {R} ^ {n \ times n} $ is the coefficient matrix, which is also sparse and / or banded, $ F \ in \ mathbb {R} ^ {n \ times s} $ is a matrix with $ s $ columns called matrix of the right hand sides and $ X \ in \ mathbb {R} ^ {n \ times s} $ is the solution of the system. An important method for the parallel solution of the above equation, is the Spike method and its variants. The Spike method is based on the divide and conquer technique and consists of two phases: a) solution of local, independent sub-problems in each processor, and b) solution of a much smaller problem which requires communication among the processors. The two phases are combined to produce the final solution $ X $. The contribution of this thesis is the acceleration of the Spike method for the solution of the matrix equation in (1) by studying, designing and implementing new, more efficient algorithmic schemes which are based on techniques used for the effective solution of linear systems with multiple right hand sides. These new algorithmic schemes were designed to improve the solving time of the linear systems as well as to provide other benefits such as more efficient use of memory.