Multilevel and algebraic multigrid methods for the higher order finite element analysis of time harmonic Maxwell's equations

The Finite Element Method (FEM) applied to wave scattering and quasi-static vector field problems in the frequency domain leads to sparse, complex-symmetric, linear systems of equations. For large problems with complicated geometries, most of the computer time and memory used by FEM goes to solving the matrix equation. Krylov subspace methods are widely used iterative methods for solving large sparse systems. They depend heavily on preconditioning to accelerate convergence. However, application of conventional preconditioners to the "curl-curl" operator which arises in vector electromagnetics does not result in a satisfactory performance and specialized preconditioning techniques are required. This thesis presents effective Multilevel and Algebraic Multigrid (AMG) preconditioning techniques for p-adaptive FEM analysis. In p-adaption, finite elements of different polynomial orders are present in the mesh and the system matrix can be structured into blocks corresponding to the orders of the basis functions. The new preconditioners are based on a p-type multilevel Schwarz (pMUS) approximate inversion of the block structured system. A V-cycle multilevel correction starts by applying Gauss-Seidel to the highest block level, then the next level down, and so on. On the other side of the V, Gauss-Seidel iterations are applied in the reverse order. At the bottom of the cycle is the lowest order system, which is usually solved exactly with a direct solver. The proposed alternative is to use Auxiliary Space Preconditioning (ASP) at the lowest level and continue the V-cycle downwards, first into a set of auxiliary, node-based spaces, then through a series of progressively smaller matrices generated by an Algebraic Multigrid (AMG). The algebraic coarsening approach is especially useful for problems with fine geometric details, requiring a very large mesh in which the bulk of the elements remain at low order. In addition, for wave problems, a "shifted Laplace" technique is applied, in which part of the ASP/AMG algorithm uses a perturbed, complex frequency. A significant convergence acceleration is achieved. The performance of Krylov algorithms is further enhanced during p-adaption by incorporation of a deflation technique. This projects out from the preconditioned system the eigenvectors corresponding to the smallest eigenvalues. The construction of the deflation subspace is based on efficient estimation of the eigenvectors from information obtained when solving the first problem in a p-adaptive sequence. Extensive numerical experiments have been performed and results are presented for both wave and quasi-static problems. The test cases considered are complicated to solve and the numerical results show the robustness and efficiency of the new preconditioners. Deflated Krylov methods preconditioned with the current Multilevel/ASP/AMG approach are always considerably faster than the reference methods and speedups of up to 10 are achieved for some test problems.La méthode des éléments finis (FEM) appliquée à la dispersion des ondes et aux problèmes de champ de vecteurs quasi-statique dans le domaine fréquentiel mène à des systèmes d'équations linéaires rares, symétriques-complexes. Pour de grands problèmes ayant des géométries complexes, la plupart du temps et de la mémoire d'ordinateur utilisé par FEM va à la résolution de l'équation de la matrice. Les méthodes itératives de Krylov sont celles largement utilisées dans la résolution de grands systèmes creux. Elles dépendent fortement des préconditionnement qui accélèrent la convergence. Toutefois, l'application de préconditionnements conventionnels à l'opérateur "rot-rot" qui surgit en électromagnétisme vectoriel n'aboutit pas à des résultats satisfaisants et des techniques de préconditionnement spécialisés sont exigées.Cette thèse présente des techniques de préconditionnement efficaces multiniveau et multigrilles algébrique (AMG) pour l'analyse p-adaptative FEM. Dans la p-adaptation, des éléments finis de différents ordres polynomiaux sont présents dans le maillage et la matrice du système peut être structurée en blocs correspondant aux ordres des fonctions de base. Les nouveaux préconditionneurs sont basés sur un type d'inversion approximative à multiniveau p Schwarz (pMUS) du système structuré de bloc. Une correction à niveaux multiples en cycle V débute par l'application de Gauss-Seidel au niveau du bloc le plus élevé, suivi par le niveau inférieur, et ainsi de suite. De l'autre côté du V, des itérations de Gauss-Seidel sont appliquées en ordre inverse. Au bas du cycle se trouve le système d'ordre le plus bas, qui est habituellement résolu exactement avec un solveur direct. L'alternative proposée est d'utiliser l'espace auxiliaire de préconditionnement (ASP) au niveau le plus bas et de poursuivre le cycle en V vers le bas, d'abord en un ensemble d'auxiliaires, basé sur les espacements de nœuds, à travers une série de plus en plus petites de matrices générées par un multigrille algébrique (AMG). L'approche de grossissement algébrique est particulièrement utile aux problèmes ayant de fins détails géométriques, nécessitant une très grande maille dans laquelle la majeure partie des éléments restent à un niveau plus bas.En outre, pour des problèmes d'onde, la technique "décalé Laplace" est appliquée, dans laquelle une partie de l'algorithme ASP/AMG utilise une fréquence complexe perturbée. Une accélération de la convergence significative est atteinte. La performance des algorithmes de Krylov est davantage renforcée au cours du p-adaptation par l'incorporation d'une technique de déflation. Cette saillie fait dépasser hors du système préconditionné, les vecteurs propres correspondants aux plus petites valeurs propres. La construction du sous-espace de déflation est basée sur une estimation efficace des vecteurs propres à partir d'informations obtenues lors de la résolution du premier problème dans une séquence p-adaptatif. Des expériences numériques approfondies ont été effectuées et les résultats sont présentés à la fois aux problèmes d'onde et quasi-statiques. Les cas de test sont considérés comme compliqués à résoudre et les résultats numériques montrent la robustesse et l'efficacité des nouveaux préconditionnements. Les méthodes de Krylov de déflation préconditionnés par l'approche multiniveaux/ASP/AMG actuelle sont toujours considérablement plus rapides que les méthodes de référence et des accélérations allant jusqu'à 10 sont atteintes pour certains problèmes de test