Parallel GMRES with a multiplicative Schwarz preconditioner - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2010

Parallel GMRES with a multiplicative Schwarz preconditioner

Résumé

In this paper, we present an hybrid solver for linear systems that combines a Krylov subspace method as accelerator with some overlapping domain decomposition method as preconditioner. The preconditioner uses an explicit formulation associated to one iteration of the classical multiplicative Schwarz method. To avoid communications and synchronizations between subdomains, the Newton-basis GMRES implementation is used as accelerator. This requires to divide the computation of the orthonormal basis in two steps: the preconditioned Newton basis is computed then it is orthogonalized. The first step is merely a sequence of matrix-vectors and solution of linear systems associated to subdomains. We describe the fine-grained parallelism that is used in these kernel operations. The second step uses a parallel implementation of dense $QR$ factorization on the resulted basis. At each application of the preconditioner operator, local systems associated to the subdomains are solved with some accuracy depending on the global physical problem. We show that this step can be further parallelized with calls to external third-party solvers. To this end, we define two levels of parallelism in the solver: the first level is intended for the computation and the communication across all the subdomains; the second level of parallelism is used inside each subdomain to solve the smaller linear systems induced by the preconditioner. Numerical experiments are performed on several problems to demonstrate the benefits of such approaches, mainly in terms of global efficiency and numerical robustness.
Dans cet article, nous présentons un solveur hybride pour la résolution des systèmes linéaires sur des architectures parallèles. Le solveur associe un accélérateur basée sur les sous-espaces de Krylov à un préconditionneur basé sur une décomposition de domaine. Le préconditionneur est défini à partir d'une formulation explicite correspondant à une itération de Schwarz multiplicatif. L'accélérateur est de type GMRES. Dans le but de réduire la communication entre les sous-domaines, nous utilisons une version parallèle de GMRES qui divise en deux étapes la construction de la base du sous-espace de Krylov associée: La première étape consiste à generer les vecteurs de la base dans un pipeline d'opérations à travers tous les processeurs. Les principales opérations ici sont les produits matrice-vecteur et les résolutions des sous-systèmes linéaires dans les sous-domaines. La deuxième étape permet d'effectuer une factorisation QR parallèle sur une matrice rectangulaire formée par les vecteurs construits précédemment; ceci permet d'obtenir une base orthogonale du sous-espace de Krylov. Les sous-systèmes issus de l'application du préconditionneur sont résolus à differents niveaux de précisions par une factorisation LU ou ILU, en fonction de la difficulté du problème sous-jacent. De plus, cette étape peut être résolue en parallèle via des appels aux solveurs parallèle externes. Pour cela, nous utilisons deux niveaux de parallélisme dans notre solveur global. Le premier niveau permet de définir les calculs et les communications à travers tous les sous-domaines. Le deuxième niveau est définie à l'intérieur de chaque sous-domaine pour la résolution des sous-systèmes issus du préconditionneur. Plusieurs tests numériques sont effectués pour valider l'efficacité de cette approche, en particulier pour les aspects d'efficacité et de robustesse.
Fichier principal
Vignette du fichier
RR-7342.pdf (422.88 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00508277 , version 1 (02-08-2010)
inria-00508277 , version 2 (23-09-2010)

Identifiants

  • HAL Id : inria-00508277 , version 1

Citer

Désiré Nuentsa Wakam, Guy-Antoine Atenekeng Kahou. Parallel GMRES with a multiplicative Schwarz preconditioner. [Research Report] RR-7342, 2010. ⟨inria-00508277v1⟩

Collections

INRIA-RRRT
167 Consultations
117 Téléchargements

Partager

Gmail Facebook X LinkedIn More