A-posteriori-steered and adaptive $p$-robust multigrid solvers

Solveurs multigrille $p$-robustes et adaptatifs guidés par des estimateurs a posteriori

Ani Miraçi (1)

1 SERENA - Simulation for the Environment: Reliable and Efficient Numerical Algorithms

In this thesis, we consider systems of linear algebraic equations arising from discretizations of second-order elliptic partial differential equations using finite elements of arbitrary polynomial degree. In Chapter 1, we propose an a posteriori estimator for the algebraic error whose construction is inherently interconnected with the design of a multigrid solver with zero pre- and only one post-smoothing step by overlapping Schwarz (block-Jacobi) methods. The main contribution of this approach consists in the two following results and their equivalence: the solver contracts the algebraic error independently of the polynomial degree ($p$-robustness); the estimator represents a two-sided $p$-robust bound on the algebraic error. The proofs of these results hold in one, two, and three space dimensions, under the minimal $H^1$-regularity of the weak solution, for quasi-uniform meshes as well as for possibly highly graded ones, and are independent of the basis of the chosen finite element space. We introduce here an optimal step-size (by line search) in the error correction stage of the multigrid. In Chapter 2, we introduce level-wise optimal step-sizes, thus maximizing the decrease of the algebraic error on each level. Under the $H^2$-regularity assumption, we prove here that the $p$-robust contraction/efficiency also hold independently of the number of mesh levels. Apart from improving the performance of the solver, the use of the level-wise step-sizes also leads to an explicit Pythagorean formula of the decrease of the algebraic error from one iteration to the next. The formula then serves as foundation of a simple and effective adaptive strategy which allows the solver to choose the necessary number of post-smoothing steps on each level. In Chapter 3, we introduce an adaptive local smoothing strategy thanks to our efficient a posteriori estimator, which has the important property of being localized level-wise and patch-wise. Thus, the estimator can detect and mark which patches of elements among all mesh levels contribute more than a user prescribed percentage to the global algebraic error (via a bulk-chasing criterion). Each iteration of the adaptive solver is here composed of two sub-steps: after a first non-adaptive V-cycle, a second adaptive and inexpensive V-cycle employs local smoothing only in the marked patches. We prove that each of these sub-steps contracts the algebraic error $p$-robustly. Finally, in Chapter 4, we provide an extension of the above results to the case of the mixed finite element method discretization in two space dimensions. A variety of numerical tests is presented to confirm the theoretical findings of this thesis, as well as to show the benefits of our $p$-robust and/or adaptive solver approaches.

Dans cette thèse, nous considérons des systèmes d’équations algébriques linéaires provenant de discrétisation d’équations aux dérivées partielles elliptiques de second ordre par des éléments finis de degré polynomial arbitraire. Dans le Chapitre 1 nous proposons un estimateur a posteriori pour l’erreur algébrique, la construction duquel est intrinsèquement liée à celle d’un solveur multigrille avec zéro pas de pré-lissage et seulement un pas de post-lissage par des méthodes de Schwarz (bloc-Jacobi) avec recouvrement. Les contributions principales de cette approche portent sur les deux résultats suivants ainsi que leur équivalence : le solveur contracte l’erreur algébrique indépendamment du degré polynomial ($p$-robustesse) ; l’estimateur représente une borne $p$-robuste supérieure et inférieure de l’erreur algébrique. Les preuves de ces résultats sont valables en un, deux, et trois dimensions d’espace, sous l’hypothèse de régularité minimale $H^1$ de la solution faible, pour des maillages quasi-uniformes ou bien des maillages issus de raffinements adaptatifs par bissection, et sont indépendantes de la base de l’espace d’éléments finis choisie. Nous introduisons ici un pas optimal (par recherche linéaire) de l’étape de correction d’erreur de multigrille. Dans le Chapitre 2 nous introduisons des pas optimaux par niveau, ainsi maximisant la réduction d’erreur algébrique à chaque niveau. Sous hypothèse de régularité $H^2$, nous prouvons ici que la contraction/efficacité $p$-robuste sont aussi indépendants du nombre de niveaux dans la hiérarchie de maillages. En plus de l’amélioration des performances du solveur, l’utilisation des pas optimaux par niveau conduit également à une formule de Pythagore explicite de la réduction de l’erreur algébrique d’une itération à l’autre. La formule sert alors de fondement pour une stratégie adaptative simple et efficace qui permet au solveur de choisir le nombre nécessaire de pas de post-lissage à chaque niveau. Dans le Chapitre 3 nous introduisons une stratégie de lissage local adaptatif grâce à notre estimateur efficace a posteriori, qui a la propriété importante d’être localisé par niveaux et par patchs d’éléments. Ainsi, l’estimateur peut détecter et marquer quels patchs d’éléments parmi tous les niveaux contribuent plus qu’un pourcentage prescrit par l’utilisateur de l’erreur algébrique globale (via un critère de type bulk-chasing). Chaque itération du solveur adaptatif est ici composée de deux sous-étapes: après un premier V-cycle non adaptatif, un deuxième V-cycle adaptatif et peu coûteux n’utilise le lissage local que dans les patchs marqués. Nous prouvons que chacune de ces sous-étapes contracte l’erreur algébrique de manière $p$-robuste. Pour terminer, dans le Chapitre 4 nous donnons des extensions des résultats ci-dessus au cadre d’éléments finis mixtes en deux dimensions d’espace. Une variété de tests numériques est présentée pour confirmer les résultats théoriques de cette thèse, ainsi que pour montrer les avantages de nos approches $p$-robustes et/ou d’adaptivité de solveurs algébriques.

Mots clés: Local smoothing; Adaptive choice of the number of smoothing steps; Adaptivity; Line search; Optimal step-sizes; Stable decomposition; $p$-robustness; A posteriori error estimate; Algebraic error; Block-Jacobi smoother; Schwarz method; Multigrid method; Algebraic iterative solver; Finite element method; Second-order elliptic problem

Mots clés: Estimateur d’erreur a posteriori; $p$-robustesse; Erreur algébrique; Lisseur bloc-Jacobi; Méthode de Schwarz; Méthode multigrille; Solveur algébrique itératif; Méthode des éléments finis; Problème elliptique de deuxième ordre; Décomposition stable; Pas optimaux; Recherche linéaire; Adaptivité; Choix adaptatif du nombre de pas de lissage; Lissage local

Domaines: Analyse numérique [math.NA]

Ani Miraçi. A-posteriori-steered and adaptive $p$-robust multigrid solvers. Numerical Analysis [math.NA]. INRIA Paris; Sorbonne Universite, 2020. English. ⟨NNT : ⟩. ⟨tel-03334270v1⟩