A GenEO Domain Decomposition method for Saddle Point problems

Frédéric Nataf; Pierre-Henri Tournier

doi:10.5802/crmeca.175

A GenEO Domain Decomposition method for Saddle Point problems

Frédéric Nataf ¹ ; Pierre-Henri Tournier ¹

¹ Laboratoire J.L. Lions, Sorbonne Université, 4 place Jussieu France

Comptes Rendus. Mécanique, Volume 351 (2023) no. S1, pp. 667-684.

Abstract
Résumé

We introduce an adaptive element-based domain decomposition (DD) method for solving saddle point problems defined as a block two by two matrix. The algorithm does not require any knowledge of the constrained space. We assume that all sub matrices are sparse and that the diagonal blocks are spectrally equivalent to a sum of positive semi definite matrices. The latter assumption enables the design of adaptive coarse space for DD methods that extends the GenEO theory (Spillane et al., 2014) to saddle point problems. Numerical results on three dimensional elasticity problems for steel-rubber structures discretized by a finite element with continuous pressure are shown for up to one billion degrees of freedom.

Nous présentons une méthode de décomposition de domaine (DD) adaptative basée pour résoudre les problèmes de points selle définis comme une matrice bloc 2x2. L’algorithme ne nécessite aucune connaissance de l’espace contraint. Nous supposons que toutes les sous-matrices sont creuses et que les blocs diagonaux sont spectralement équivalents à une somme de matrices semi-définies positives. Cette dernière hypothèse permet de concevoir un espace grossier adaptatif pour les méthodes DD qui étend la théorie de GenEO (Spillane et al., 2014) aux problèmes de points de selle. Des résultats numériques sur des problèmes d’élasticité tridimensionnels pour des structures acier-caoutchouc discrétisées avec une pression continue sont montrés jusqu’à un milliard de degrés de liberté.

Received: 2023-01-18
Accepted: 2023-01-19
Online First: 2023-03-27
Published online: 2024-04-26

DOI: 10.5802/crmeca.175

Keywords: domain decomposition method, nearly incompressible elasticity, high performance computing, saddle point problem, coarse space, multiscale finite element, Schur complement
Mot clés : Méthode de décomposition de domaine, élasticité quasi incompressible, calcul haute performance, problème de point selle, espace grossier, éléments finis multi échelle, complément de Schur

Author's affiliations:

Frédéric Nataf ¹; Pierre-Henri Tournier ¹

¹ Laboratoire J.L. Lions, Sorbonne Université, 4 place Jussieu France

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{CRMECA_2023__351_S1_667_0,
     author = {Fr\'ed\'eric Nataf and Pierre-Henri Tournier},
     title = {A {GenEO} {Domain} {Decomposition} method for {Saddle} {Point} problems},
     journal = {Comptes Rendus. M\'ecanique},
     pages = {667--684},
     publisher = {Acad\'emie des sciences, Paris},
     volume = {351},
     number = {S1},
     year = {2023},
     doi = {10.5802/crmeca.175},
     language = {en},
}

TY  - JOUR
AU  - Frédéric Nataf
AU  - Pierre-Henri Tournier
TI  - A GenEO Domain Decomposition method for Saddle Point problems
JO  - Comptes Rendus. Mécanique
PY  - 2023
SP  - 667
EP  - 684
VL  - 351
IS  - S1
PB  - Académie des sciences, Paris
DO  - 10.5802/crmeca.175
LA  - en
ID  - CRMECA_2023__351_S1_667_0
ER  -

%0 Journal Article
%A Frédéric Nataf
%A Pierre-Henri Tournier
%T A GenEO Domain Decomposition method for Saddle Point problems
%J Comptes Rendus. Mécanique
%D 2023
%P 667-684
%V 351
%N S1
%I Académie des sciences, Paris
%R 10.5802/crmeca.175
%G en
%F CRMECA_2023__351_S1_667_0

Frédéric Nataf; Pierre-Henri Tournier. A GenEO Domain Decomposition method for Saddle Point problems. Comptes Rendus. Mécanique, Volume 351 (2023) no. S1, pp. 667-684. doi : 10.5802/crmeca.175. https://comptes-rendus.academie-sciences.fr/mecanique/articles/10.5802/crmeca.175/

References
Cited by

[1] Juan Galvis; Yalchin Efendiev Domain decomposition preconditioners for multiscale flows in high contrast media: reduced dimension coarse spaces, Multiscale Model. Simul., Volume 8 (2010) no. 5, pp. 1621-1644 | DOI | MR | Zbl

[2] Frédéric Nataf; Hua Xiang; Victorita Dolean; Nicole Spillane A coarse space construction based on local Dirichlet to Neumann maps, SIAM J. Sci. Comput., Volume 33 (2011) no. 4, pp. 1623-1642 | DOI | MR | Zbl

[3] Yalchin Efendiev; Juan Galvis; Raytcho Lazarov; Joerg Willems Robust domain decomposition preconditioners for abstract symmetric positive definite bilinear forms, ESAIM, Math. Model. Numer. Anal., Volume 46 (2012) no. 5, pp. 1175-1199 | DOI | Numdam | MR | Zbl

[4] Pierre Jolivet; Victorita Dolean; Frédéric Hecht; Frédéric Nataf; Christophe Prud’homme; Nicole Spillane High performance domain decomposition methods on massively parallel architectures with freefem++, J. Numer. Math., Volume 20 (2012) no. 3-4, pp. 287-302 | MR | Zbl

[5] Nicole Spillane; Daniel J. Rixen Automatic spectral coarse spaces for robust finite element tearing and interconnecting and balanced domain decomposition algorithms, Int. J. Numer. Methods Eng. (2013) no. 11, pp. 953-990 | DOI | MR | Zbl

[6] Victorita Dolean; Pierre Jolivet; Frédéric Nataf An Introduction to Domain Decomposition Methods: algorithms, theory and parallel implementation, Other Titles in Applied Mathematics, 144, Society for Industrial and Applied Mathematics, 2015 | DOI | Zbl

[7] Nicole Spillane Robust domain decomposition methods for symmetric positive definite problems, Ph. D. Thesis, Université Pierre et Marie Curie - Paris VI, Paris, France (2014)

[8] Joseph E. Pasciak; J. Zhao Overlapping Schwarz methods in H(curl) on polyhedral domains, J. Numer. Math., Volume 10 (2002) no. 3, pp. 221-234 | MR | Zbl

[9] Axel Klawonn An optimal preconditioner for a class of saddle point problems with a penalty term, SIAM J. Sci. Comput., Volume 19 (1998) no. 2, pp. 540-552 | DOI | MR | Zbl

[10] Luca F. Pavarino; Olof B. Widlund Balancing Neumann-Neumann methods for incompressible Stokes equations, Commun. Pure Appl. Math., Volume 55 (2002) no. 3, pp. 302-335 | DOI | MR | Zbl

[11] Andrea Toselli; Olof B. Widlund Domain Decomposition Methods - Algorithms and Theory, Springer Series in Computational Mathematics, 34, Springer, 2005 | DOI | Zbl

[12] Ryadh Haferssas; Pierre Jolivet; Frédéric Nataf An Additive Schwarz Method Type Theory for Lions’s Algorithm and a Symmetrized Optimized Restricted Additive Schwarz Method, SIAM J. Sci. Comput., Volume 39 (2017) no. 4, p. A1345-A1365 | DOI | Zbl

[13] Olof B. Widlund; Stefano Zampini; Simone Scacchi; Luca F. Pavarino Block FETI–DP/BDDC preconditioners for mixed isogeometric discretizations of three-dimensional almost incompressible elasticity, Math. Comput., Volume 90 (2021) no. 330, pp. 1773-1797 | DOI | Zbl

[14] Xuemin Tu; Jing Li A FETI-DP type domain decomposition algorithm for three-dimensional incompressible Stokes equations, SIAM J. Numer. Anal., Volume 53 (2015) no. 2, pp. 720-742 | Zbl

[15] Malcolm F. Murphy; Gene H. Golub; Andrew J. Wathen A note on preconditioning for indefinite linear systems, SIAM J. Sci. Comput., Volume 21 (2000) no. 6, pp. 1969-1972 | DOI | MR | Zbl

[16] Michele Benzi; Gene H. Golub; Jörg Liesen Numerical solution of saddle point problems, Acta Numer., Volume 14 (2005), pp. 1-137 | DOI | MR | Zbl

[17] Eric de Sturler; Jörg Liesen Block-diagonal and constraint preconditioners for nonsymmetric indefinite linear systems. I. Theory, SIAM J. Sci. Comput., Volume 26 (2005) no. 5, pp. 1598-1619 | DOI | MR | Zbl

[18] Tyrone Rees; Michael Wathen An element-based preconditioner for mixed finite element problems, SIAM J. Sci. Comput., Volume 43 (2020) no. 5, p. S884-S907 | DOI | MR | Zbl

[19] Jacques Cahouet; Jean-Paul Chabard Some fast 3d finite element solvers for the generalized stokes problem, Int. J. Numer. Methods Fluids, Volume 8 (1988) no. 8, pp. 869-895 | DOI | Zbl

[20] Ralf Hiptmair Multigrid Method for H(div) in Three Dimensions, Electron. Trans. Numer. Anal., Volume 6 (1997), pp. 133-152 | MR | Zbl

[21] Ralf Hiptmair Multigrid method for Maxwell’s equations, SIAM J. Numer. Anal., Volume 36 (1998) no. 1, pp. 204-225 | DOI | MR | Zbl

[22] Douglas N. Arnold; Richard S. Falk; Ragnar Winther Multigrid in H(div) and H(curl), Numer. Math., Volume 85 (2000) no. 2, pp. 197-217 | DOI | MR | Zbl

[23] Stefan Reitzinger; Joachim Schöberl An algebraic multigrid method for finite element discretizations with edge elements, Numer. Linear Algebra Appl., Volume 9 (2002) no. 3, pp. 223-238 | DOI | MR | Zbl

[24] Patrick E. Farrell; Lawrence Mitchell; Florian Wechsung An Augmented Lagrangian Preconditioner for the 3D Stationary Incompressible Navier–Stokes Equations at High Reynolds Number, SIAM J. Sci. Comput., Volume 41 (2019) no. 5, p. A3073-A3096 | DOI | MR | Zbl

[25] Daniel Drzisga; Lorenz John; Ulrich Rüde; Barbara Wohlmuth; Walter Zulehner On the analysis of block smoothers for saddle point problems, SIAM J. Matrix Anal. Appl., Volume 39 (2018) no. 2, pp. 932-960 | DOI | MR | Zbl

[26] Roland Glowinski; Patrick Le Tallec Numerical Solution of Problems in Incompressible Finite Elasticity by Augmented Lagrangian Methods. I. Two-dimensional and Axisymmetric Problems, SIAM J. Appl. Math., Volume 42 (1982), pp. 400-429 | DOI | MR | Zbl

[27] Roland Glowinski; Patrick Le Tallec Augmented Lagrangian and operator-splitting methods in nonlinear mechanics, SIAM Studies in Applied Mathematics, 9, Society for Industrial and Applied Mathematics, 1989 | DOI | Zbl

[28] Michel Fortin; Roland Glowinski Augmented Lagrangian methods: applications to the numerical solution of boundary-value problems, Studies in Mathematics and its Applications, 15, Elsevier, 2000

[29] Roland Glowinski; Patrick Le Tallec Numerical Solution of Problems in Incompressible Finite Elasticity by Augmented Lagrangian Methods II. Three-Dimensional Problems, SIAM J. Appl. Math., Volume 44 (1984), pp. 710-733 | DOI | MR | Zbl

[30] Michele Benzi; Andrew J. Wathen Some preconditioning techniques for saddle point problems, Model order reduction: theory, research aspects and applications (Mathematics in Industry), Volume 13, Springer, 2008, pp. 195-211 | MR | Zbl

[31] Nicole Spillane; Victorita Dolean; Patrice Hauret; Frédéric Nataf; Clemens Pechstein; Robert Scheichl Abstract robust coarse spaces for systems of PDEs via generalized eigenproblems in the overlaps, Numer. Math., Volume 126 (2014) no. 4, pp. 741-770 | DOI | MR | Zbl

[32] Sergeĭ V. Nepomnyaschikh Mesh theorems of traces, normalizations of function traces and their inversions, Sov. J. Numer. Anal. Math. Model., Volume 6 (1991), pp. 223-242 | MR | Zbl

[33] Michael Griebel; Peter Oswald On the abstract theory of additive and multiplicative Schwarz algorithms, Numer. Math., Volume 70 (1995) no. 2, pp. 163-180 | DOI | MR | Zbl

[34] J. F. Bourgat; Roland Glowinski; Patrick Le Tallec; Marina Vidrascu Variational formulation and algorithm for trace operator in domain decomposition calculations, Domain Decomposition Methods (T. Chan; R. Glowinski; J. Périaux; O. Widlund, eds.), Society for Industrial and Applied Mathematics, 1989, pp. 3-16 | Zbl

[35] Charbel Farhat; Francois-Xavier Roux A method of Finite Element Tearing and Interconnecting and its parallel solution algorithm, Int. J. Numer. Meth. Eng., Volume 32 (1991) no. 6, pp. 1205-1227 | DOI | MR | Zbl

[36] Franco Brezzi; Michel Fortin Mixed and hybrid finite element methods, Springer Series in Computational Mathematics, 15, Springer, 1991 | DOI | Zbl

[37] G. Karypis; V. Kumar METIS: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices (1998) (http://glaros.dtc.umn.edu/gkhome/views/metis) (Technical report)

[38] Frédéric Hecht New development in Freefem++, J. Numer. Math., Volume 20 (2012) no. 3-4, pp. 251-265 | MR | Zbl

[39] P.-H. Tournier; Frédéric Nataf FFDDM: Freefem domain decomposition method, 2019 (https://doc.freefem.org/documentation/ffddm/index.html)

[40] Patrick R. Amestoy; Iain S. Duff; Jean-Yves L’Excellent; Jacko Koster A fully asynchronous multifrontal solver using distributed dynamic scheduling, SIAM J. Matrix Anal. Appl., Volume 23 (2001) no. 1, pp. 15-41 | DOI | MR | Zbl

[41] Richard B. Lehoucq; Danny C. Sorensen; C. Yang ARPACK users’ guide: solution of large-scale eigenvalue problems with implicitly restarted Arnoldi methods, Software - Environments - Tools, 6, Society for Industrial and Applied Mathematics, 1998 | DOI | Zbl

[42] C. Chevalier; F. Pellegrini PT-SCOTCH: a tool for efficient parallel graph ordering, Parallel Comput., Volume 34 (2008) no. 6-8, pp. 318-331 | DOI | MR

[43] Satish Balay; William D. Gropp; Lois Curfman McInnes; Barry F. Smith Efficient management of parallelism in object oriented numerical software libraries, Modern Software Tools in Scientific Computing, Birkhäuser, 1997, pp. 163-202 | DOI | Zbl

[44] Pierre Jolivet; Frédéric Nataf HPDDM: High-Performance Unified framework for Domain Decomposition methods, MPI-C++ library, 2014 (https://github.com/hpddm/hpddm)

[45] Pierre Jolivet; Jose E. Roman; Stefano Zampini KSPHPDDM and PCHPDDM: Extending PETSc with advanced Krylov methods and robust multilevel overlapping Schwarz preconditioners, Comput. Math. Appl., Volume 84 (2021), pp. 277-295 | DOI | MR | Zbl

[46] Satish Balay; S. Abhyankar; M. F. Adams; J. Brown; P. Brune; K. Buschelman; V. Eijkhout; William D. Gropp; D. Kaushik; M. G. Knepley; Lois C. McInnes; K. Rupp; B. F. Smith; H. Zhang PETSc users manual (2014) no. ANL-95/11 (Technical report)

[47] Yalchin Efendiev; Juan Galvis; Thomas Y. Hou Generalized multiscale finite element methods (GMsFEM), J. Comput. Phys., Volume 251 (2013), pp. 116-135 | DOI | MR | Zbl

[48] Patrick Jenny; S. H. Lee; Hamdi A. Tchelepi Adaptive multiscale finite-volume method for multiphase flow and transport in porous media, Multiscale Model. Simul., Volume 3 (2005) no. 1, pp. 50-64 | DOI | MR

[49] Chupeng Ma; Robert Scheichl; Tim Dodwell Novel design and analysis of generalized FE methods based on locally optimal spectral approximations (2021) (https://arxiv.org/abs/2103.09545)

Cited by Sources:

Comments - Policy