Academic literature on the topic 'Préconditionneurs'

Cette thèse est un ensemble de contributions visant à développer des procédés rapides de résolution de problèmes de diffraction d'ondes acoustiques ou électromagnétiques en régime harmonique. La technique essentielle consiste à coupler l'approche par équations intégrales à la méthode des conditions de radiation sur le bord (On Surface Radiation Condition ou OSRC) donnant des approximations microlocales de l'opérateur Dirichlet-Neumann en régime de haute-fréquence. Plus précisément, les OSRCs sont utilisées comme des accélérateurs de convergence des algorithmes itératifs considérés pour la résolution des formulations intégrales. Les études se répartissent en deux axes principaux: les surfaces ouvertes et les surfaces fermées. Dans le cas des surfaces ouvertes, les OSRCs constituent de nouvelles classes de préconditionneurs analytiques de type Calderon efficaces. Dans le cas des surfaces fermées, les OSRCs jouent le rôle d'opérateurs régularisants et conduisent à la construction d'équations intégrales de type Fredholm de seconde espèce bien adaptées à une résolution itérative. La construction de ces formulations est basée sur l'obtention d'un bon regroupement des valeurs spectrales des opérateurs associés. Des tests numériques illustrent la théorie et montrent une convergence rapide des solveurs itératifs indépendante du raffinement de maillage et de la montée en fréquence pour divers obstacles en dimension deux et trois<br>This thesis deals with fast numerical processes to solve scattering problems of acoustic or electromagnetic waves. The essential used technique consists in coupling the integral equations method with the On-Surface Radiation Conditions (OSRC) method deriving microlocal approximations of the Dirichlet-Neumann operator in the high frequency regime. More particularly, we use OSRC to accelerate the convergence of the iterative methods considered to solve integral equations. We develop two studies : open surfaces and closed surfaces. In the case of open surfaces, OSRC represent some efficient analytic Calderon-type preconditioners. In the case of closed surfaces, OSRC designate some regularizing operators and lead to the construction of second-kind Fredholm integral equations. These equations are well-adapted to an iterative solution. Their construction is based on obtaining an excellent eigenvalues clustering of the associated operators. Two-dimensional and three-dimensional numerical tests confirm the theoritical analysis. They show that good convergence rates of the iterative solvers are attained. The convergence is independent of the mesh refinement and of the wave number

L'auteur etudie la resolution de problemes d'optimisation non lineaire de grande taille a l'aide de methodes utilisant au mieux leur structure. En particulier, la propriete de separabilite partielle est utilisee. Une methode typique de minimisation pour des problemes non lineaires consiste a resoudre approximativement une suite de sous-problemes linearises. La propriete de separabilite partielle peut etre exploitee par des methodes iteratives pour la resolution de ces sous-problemes grace a l'utilisation de preconditionneurs adaptes. L'auteur s'interesse aux preconditionneurs element-par-element qui refletent la structure du probleme, et a plusieurs variantes interessantes. Ces preconditionneurs possedent plusieurs avantages. Par exemple, la matrice n'a pas besoin d'etre assemblee et le degre de parallelisme est eleve. De plus ces methodes peuvent etre appliquees a des problemes plus generaux que des problemes d'optimisation (par exemple les problemes d'elements finis) et en fait a tous les problemes ou la matrice du systeme lineaire a resoudre s'exprime comme une somme de matrices elementaires, chaque matrice elementaire n'impliquant qu'un petit nombre de variables. Il est demontre que l'efficacite de ces methodes peut etre considerablement amelioree en amalgamant des paires d'elements avant d'appliquer les preconditionneurs ou en utilisant des techniques de partitionnement de graphe, ce qui donne lieu a des methodes iteratives par blocs. Des experimentations sur des problemes reels et des comparaisons avec d'autres techniques classiques prouvent l'interet de ces approches et leur efficacite sur des calculateurs vectoriels et paralleles, a memoire partagee. Enfin, un algorithme d'optimisation - une methode de newton tronquee - utilisant ces techniques est propose et experimente sur une gamme de problemes d'optimisation

Le Contexte de ce travail est l'algèbre linéaire numérique. Plus précisément, on s'est intéressé à des préconditionnements pour les méthodes de Krylov, basés sur une connaissance de certains espaces propres. Ces techniques sont en particulier très utiles lorsque l'on résout une séquence de systèmes linéaires avec la même matrice mais différents second membres. L'information sur les espaces propres est extraite dans une phase d'initialisation, ou au cours de la résolution du premier système, et utilisée dans la résolution des systèmes suivants. L'approche développée dans cette thèse se base sur l'utilisation des filtres polynomiaux de Tchebycheff et sur la construction de préconditionneurs spectraux pour l'accélération des méthodes de Krylov.

Les méthodes d'éléments finis p-version sont basées sur des espaces de fonctions continues, polynomiales par morceaux dont les restrictions sont de degré p élevé sur chaque élément d'un maillage de (le domaine de l'équation aux dérivées partielles). Ces espaces sont optimaux pour l'approximation des espaces de Sobolev par des espaces de dimension finie. Ces méthodes utilisent des bases hiérarchiques dans un but adaptatif. Différentes bases ont été proposées jusqu'alors ; l'une d'elles s'impose actuellement : les matrices construites avec cette base sont tres creuses. Pour cette base construite à partir des intégrales mèmes (pour les problèmes d'ordre 2m) des polynomes de Legendre normalisés, nous avons établi les conditionnements en O(p 4(md-k)) des matrices associées au produit scalaire Hk obtenues en dimension d sur un élément. On en déduit par exemple sur , pour m=k=1 et d=2 (probleme elliptique bi-dimentionnel): (1) C1p4 ≤ K(Ap) ≤ C2p4(1+log2(p)). Nous avons ensuite montré qu'il existe des préconditionneurs multiniveaux en O(p2). Ce type de préconditionneurs s'appuie sur une décomposition L2 orthogonale dont nous avons montré que le calcul ne peut pas être raisonnablement approché dans le cadre des bases hiérarchiques. Nous avons enfin etudié un préconditionnement plus simple, à savoir le préconditionnement par la diagonale pour les problêmes d'ordre 2 et 4. Nous prouvons son efficacité : dans tous les cas etudiés, le préconditionnement diagonal permet d'obtenir un conditionnement qui se comporte comme la racine du conditionnement initial, et ce résultat asymptotique se vérifie numériquement dès les plus bas degrés (2, 3, 4. . . ). On en déduit par exemple sur , pour m=k=1 et d=2 (voir (1)) : (2) C1p2 ≤ K(Dp-1/2 ApDp-1/2) ≤ C2p2(1+log2(p)).

La thèse a pour objectif le développement de méthodes performantes pour la résolution de problèmes non linéaires ne mécanique des solides. Il est coutume d'utiliser une méthode de type Newton qui conduit à la résolution d'une séquence de systèmes linéaires. De plus, la prise en compte des relations linéaires imposées à l'aide de multiplicateurs de Lagrange confère aux matrices une structure de point-selle. Dans un cadre plus général, nous proposons, étudions et illustrons deux classes d'enrichissement de préconditionneurs (limited memory preconditioners) pour la résolution de séquences de systèmes linéaires par une méthode de Krylov. La première est un extension au cas symétrique indéfini d'une méthode existante, développée initialement dans le cadre symétrique défini positif. La seconde est plus générale dans le sens où elle s'applique aus systèmes non symétriques. Ces deux familles peuvent être interprétées comme des variantes par blocs de formules de mise à jour utilisées dans différentes méthodes d'optimisation. Ces techniques ont été développées dans le logiciel de mécanique des solides Code_Aster (dans un environnement parallèle distribué via la bibliothèque PETSc) et sont illustrées sur plusieurs études industrielles. Les gains obtenus en terme de coût de calcul sont significatifs (jusqu'à 50%), pour un surcoût mémoire négligeable<br>The thesis aims at developing efficient numerical methods to solve nonlinear problems arising un solid mechanics. In this field, Newton methods are currently used, requiring the solution of a sequence of linear systems. Furthermore, the imposed linear relations are dualized with the Lagrange multipliers, leading to matrices with a saddle point structure. In a more general framework, we propose two classes of preconditioners (named limited memory preconditioners) to solve sequences of linear systems with a Krylov subspace method. The first class is based on an extension of a method initially developed for symmetric positive definite matrices to the symmetric indefinite case. Both families can be interpreted as block variants of updating formulas used in numerical optimization. They have been implemented into the Code_Aster solid mechanics software (in a parallel distributed environement using the PETSc library). These new preconditioning strategies are illustrated on several industrial applications. We obtain significant gains in computational cost (up to 50%) at a marginal overcost in memory

Le but de cette thèse est de développer une méthode de volumes finis qui s'applique à une classe de maillages beaucoup plus grande que celle des méthodes classiques, limitées par des conditions d'orthogonalité très restrictives. On construit des opérateurs différentiels discrets agissant sur les trois maillages décalés nécessaires à la construction de la méthode. Ces opérateurs vérifient des propriétés discrètes analogues à celles des opérateurs continus. La méthode est tout d'abord appliquée au problème divergence-rotationnel qui peut etre considéré comme une brique du problème de Stokes. Ensuite, le problème de Stokes est discrétisé avec diverses conditions aux limites. Par ailleurs, il est bien connu que lorsque le domaine est polygonal et non-convexe, l'ordre de convergence des méthodes numériques se dégrade. Par conséquent, nous avons étudié sous quelles conditions un raffinement local approprié permet de restaurer l'ordre de convergence optimal. Enfin, nous avons discrétisé le problème non-linéaire de Navier-Stokes, en utilisant la formulation rotationnelle du terme de convection, associée à la pression de Bernoulli. Par un algorithme itératif, nous sommes amenés à résoudre un problème de point-selle à chaque itération, pour lequel nous testons quelques préconditionneurs issus des éléments finis, que l'on adapte (quand c'est possible) à la méthode. Chaque problème est illustré par des cas tests numériques sur des maillages "arbitraires", tels que des maillages fortement non-conformes.

Cette thèse vise à concevoir des solveurs efficaces pour résoudre des systèmes linéaires, résultant des problèmes d'optimisation sous contraintes dans certaines applications de dynamique des structures et vibration (la corrélation calcul-essai, la localisation d'erreur, le modèle hybride, l'évaluation des dommages, etc.). Ces applications reposent sur la résolution de problèmes inverses, exprimés sous la forme de la minimisation d'une fonctionnelle en énergie. Cette fonctionnelle implique à la fois, des données issues d'un modèle numérique éléments finis, et des essais expérimentaux. Ceci conduit à des modèles de haute qualité, mais les systèmes linéaires point-selle associés, sont coûteux à résoudre. Nous proposons deux classes différentes de méthodes pour traiter le système. La première classe repose sur une méthode de factorisation directe profitant de la topologie et des propriétés spéciales de la matrice point-selle. Après une première renumérotation pour regrouper les pivots en blocs d'ordre 2. L'élimination de Gauss est conduite à partir de ces pivots et en utilisant un ordre spécial d'élimination réduisant le remplissage. Les résultats numériques confirment des gains significatifs en terme de remplissage, jusqu'à deux fois meilleurs que la littérature pour la topologie étudiée. La seconde classe de solveurs propose une approche à double projection du système étudié sur le noyau des contraintes, en faisant une distinction entre les contraintes cinématiques et celles reliées aux capteurs sur la structure. La première projection est explicite en utilisant une base creuse du noyau. La deuxième est implicite. Elle est basée sur l'emploi d'un préconditionneur contraint avec des méthodes itératives de type Krylov. Différentes approximations des blocs du préconditionneur sont proposées. L'approche est implémentée dans un environnement distribué parallèle utilisant la bibliothèque PETSc. Des gains significatifs en terme de coût de calcul et de mémoire sont illustrés sur plusieurs applications industrielles<br>This thesis aims at designing efficient numerical solution methods to solve linear systems, arising in constrained optimization problems in some structural dynamics and vibration applications (test-analysis correlation, model error localization,hybrid model, damage assessment, etc.). These applications rely on solving inverse problems, by means of minimization of an energy-based functional. This latter involves both data from a numerical finite element model and from experimental tests, which leads to high quality models, but the associated linear systems, that have a saddle-point coefficient matrices, are long and costly to solve. We propose two different classes of methods to deal with these problems. First, a direct factorization method that takes advantage of the special structures and properties of these saddle point matrices. The Gaussian elimination factorization is implemented in order to factorize the saddle point matrices block-wise with small blocks of orders 2 and using a fill-in reducing topological ordering. We obtain significant gains in memory cost (up to 50%) due to enhanced factors sparsity in comparison to literature. The second class is based on a double projection of the generated saddle point system onto the nullspace of the constraints. The first projection onto the kinematic constraints is proposed as an explicit process through the computation of a sparse null basis. Then, we detail the application of a constraint preconditioner within a Krylov subspace solver, as an implicit second projection of the system onto the nullspace of the sensors constraints. We further present and compare different approximations of the constraint preconditioner. The approach is implemented in a parallel distributed environment using the PETSc library. Significant gains in computational cost and memory are illustrated on several industrial applications

La performance d'un algorithme sur une architecture donnée dépend à la fois de la vitesse à laquelle le processeur effectue des opérations à virgule flottante (flops) et de la vitesse d'accès à la mémoire et au disque. Etant donné que le coût de la communication est beaucoup plus élevé que celui des opérations arithmétiques, celle-là forme un goulot d'étranglement dans les algorithmes numériques. Récemment, des méthodes de sous-espace de Krylov basées sur les méthodes 's-step' ont été développées pour réduire les communications. En effet, très peu de préconditionneurs existent pour ces méthodes, ce qui constitue une importante limitation. Dans cette thèse, nous présentons le préconditionneur nommé ''Communication-Avoiding ILU0'', pour la résolution des systèmes d’équations linéaires (Ax=b) de très grandes tailles. Nous proposons une nouvelle renumérotation de la matrice A ('alternating min-max layers'), avec laquelle nous montrons que le préconditionneur en question réduit la communication. Il est ainsi possible d’effectuer « s » itérations d’une méthode itérative préconditionnée sans communication. Nous présentons aussi deux nouvelles méthodes itératives, que nous nommons 'multiple search direction with orthogonalization CG' (MSDO-CG) et 'long recurrence enlarged CG' (LRE-CG). Ces dernières servent à la résolution des systèmes linéaires d’équations de très grandes tailles, et sont basées sur l’enrichissement de l’espace de Krylov par la décomposition du domaine de la matrice A<br>The performance of an algorithm on any architecture is dependent on the processing unit’s speed for performing floating point operations (flops) and the speed of accessing memory and disk. As the cost of communication is much higher than arithmetic operations, and since this gap is expected to continue to increase exponentially, communication is often the bottleneck in numerical algorithms. In a quest to address the communication problem, recent research has focused on communication avoiding Krylov subspace methods based on the so called s-step methods. However there are very few communication avoiding preconditioners, and this represents a serious limitation of these methods. In this thesis, we present a communication avoiding ILU0 preconditioner for solving large systems of linear equations (Ax=b) by using iterative Krylov subspace methods. Our preconditioner allows to perform s iterations of the iterative method with no communication, by applying a heuristic alternating min-max layers reordering to the input matrix A, and through ghosting some of the input data and performing redundant computation. We also introduce a new approach for reducing communication in the Krylov subspace methods, that consists of enlarging the Krylov subspace by a maximum of t vectors per iteration, based on the domain decomposition of the graph of A. The enlarged Krylov projection subspace methods lead to faster convergence in terms of iterations and to parallelizable algorithms with less communication, with respect to Krylov methods. We discuss two new versions of Conjugate Gradient, multiple search direction with orthogonalization CG (MSDO-CG) and long recurrence enlarged CG (LRE-CG)