Recent advances in domain decomposition methods for large-scale saddle point problems

Frédéric Nataf; Pierre-Henri Tournier

doi:10.5802/crmeca.130

Recent advances in domain decomposition methods for large-scale saddle point problems

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

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

Comptes Rendus. Mécanique, Online first (2022), pp. 1-15.

Abstract
Résumé

Scalability of parallel solvers for problems with high heterogeneities relies on adaptive coarse spaces built from generalized eigenvalue problems in the subdomains. The corresponding theory is powerful and flexible but the development of an efficient parallel implementation is challenging. We report here on recent advances in adaptive coarse spaces and on their open source implementations in domain specific languages such as FreeFem, focusing on a new domain decomposition for saddle point formulations with some numerical tests.

L’extensibilité des solveurs parallèles pour les problèmes à forte hétérogénéité repose sur des espaces grossiers adaptatifs construits à partir de problèmes de valeurs propres généralisés dans les sous-domaines. La théorie correspondante est puissante et flexible mais le développement d’une implémentation parallèle efficace est un défi. Nous présentons ici les avancées récentes en matière d’espaces grossiers adaptatifs et leurs implémentations open source dans des langages spécifiques au domaine tels que FreeFem, en nous concentrant sur une nouvelle décomposition de domaine pour les formulations de points de selle avec des tests numériques.

Received: 2021-12-24
Accepted: 2022-09-08
Online First: 2022-10-03

DOI: 10.5802/crmeca.130

Keywords: High performance computing, Saddle point problem, Domain decomposition methods, Nearly incompressible elasticity, Multilevel methods
Mot clés : Calcul haute performance, Problème de point selle, Méthodes de décomposition de domaine, Elasticité presque incompressible, Méthode multi niveaux

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_2022__350_S1_A5_0,
     author = {Fr\'ed\'eric Nataf and Pierre-Henri Tournier},
     title = {Recent advances in domain decomposition methods for large-scale saddle point problems},
     journal = {Comptes Rendus. M\'ecanique},
     publisher = {Acad\'emie des sciences, Paris},
     year = {2022},
     doi = {10.5802/crmeca.130},
     language = {en},
     note = {Online first},
}

TY  - JOUR
AU  - Frédéric Nataf
AU  - Pierre-Henri Tournier
TI  - Recent advances in domain decomposition methods for large-scale saddle point problems
JO  - Comptes Rendus. Mécanique
PY  - 2022
PB  - Académie des sciences, Paris
N1  - Online first
DO  - 10.5802/crmeca.130
LA  - en
ID  - CRMECA_2022__350_S1_A5_0
ER  -

%0 Journal Article
%A Frédéric Nataf
%A Pierre-Henri Tournier
%T Recent advances in domain decomposition methods for large-scale saddle point problems
%J Comptes Rendus. Mécanique
%D 2022
%I Académie des sciences, Paris
%Z Online first
%R 10.5802/crmeca.130
%G en
%F CRMECA_2022__350_S1_A5_0

Frédéric Nataf; Pierre-Henri Tournier. Recent advances in domain decomposition methods for large-scale saddle point problems. Comptes Rendus. Mécanique, Online first (2022), pp. 1-15. doi : 10.5802/crmeca.130.

References
Cited by

[1] J. Moulin; P. Jolivet; O. Marquet Augmented Lagrangian preconditioner for large-scale hydrodynamic stability analysis, Comput. Methods Appl. Mech. Eng., Volume 351 (2019), pp. 718-743 | DOI | MR | Zbl

[2] R. Haferssas; P. Jolivet; S. Rubino Efficient and scalable discretization of the Navier–Stokes equations with LPS modeling, Comput. Methods Appl. Mech. Eng., Volume 333 (2018), pp. 371-394 | DOI | MR | Zbl

[3] J. Cahouet; J.-P. 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

[4] R. Hiptmair Multigrid method for H(div) in three dimensions, Electron. Trans. Numer. Anal., Volume 6 (1997) no. 1, pp. 133-152 | MR | Zbl

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

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

[7] S. Reitzinger; J. 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

[8] P. E. Farrell; L. Mitchell; F. 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

[9] D. Drzisga; L. John; U. Rude; B. Wohlmuth; W. 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

[10] F. Feppon; G. Allaire; C. Dapogny; P. Jolivet Topology optimization of thermal fluid–structure systems using body-fitted meshes and parallel computing, J. Comput. Phys., Volume 417 (2020), 109574 | DOI | MR | Zbl

[11] N. Spillane; V. Dolean; P. Hauret; F. Nataf; C. Pechstein; R. 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

[12] H. A. Schwarz Über einen Grenzübergang durch alternierendes Verfahren, Vierteljahrsschr. Nat.forsch. Ges. Zür., Volume 15 (1870), pp. 272-286

[13] M. J. Gander Schwarz methods over the course of time, Electron. Trans. Numer. Anal., Volume 31 (2008), pp. 228-255 | MR | Zbl

[14] P.-L. Lions On the Schwarz alternating method. III: A variant for nonoverlapping subdomains, First International Symposium on Domain Decomposition Methods for Partial Differential Equations (T. F. Chan; R. Glowinski; J. Périaux; O. Widlund, eds.), SIAM, Philadelphia, PA (1990) | Zbl

[15] P.-L. Lions On the Schwarz alternating method. II, Domain Decomposition Methods (T. Chan; R. Glowinski; J. Périaux; O. Widlund, eds.), SIAM, Philadelphia, PA, 1989, pp. 47-70 | Zbl

[16] X.-C. Cai; M. Sarkis A restricted additive Schwarz preconditioner for general sparse linear systems, SIAM J. Sci. Comput., Volume 21 (1999), pp. 239-247 | MR | Zbl

[17] F. Nataf; H. Xiang; V. Dolean; N. 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

[18] S. V. Nepomnyaschikh Mesh theorems of traces, normalizations of function traces and their inversions, Sov. J. Numer. Anal. Math. Model., Volume 6 (1991), pp. 1-25 | MR | Zbl

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

[20] R. A. Nicolaides Deflation of conjugate gradients with applications to boundary value problems, SIAM J. Numer. Anal., Volume 24 (1987) no. 2, pp. 355-365 | DOI | MR | Zbl

[21] Y. A. Erlangga; R. Nabben Deflation and balancing preconditioners for Krylov subspace methods applied to nonsymmetric matrices, SIAM J. Matrix Anal. Appl., Volume 30 (2008) no. 2, pp. 684-699 | DOI | MR | Zbl

[22] J. Tang; R. Nabben; C. Vuik; Y. Erlangga Comparison of two-level preconditioners derived from deflation, domain decomposition and multigrid methods, J. Sci. Comput., Volume 39 (2009) no. 3, pp. 340-370 | DOI | MR | Zbl

[23] J. Erhel; F. Guyomarc’h An augmented conjugate gradient method for solving consecutive symmetric positive definite linear systems, SIAM J. Matrix Anal. Appl., Volume 21 (2000) no. 4, pp. 1279-1299 | DOI | MR | Zbl

[24] M. L. Parks; E. de Sturler; G. Mackey; D. D. Johnson; S. Maiti Recycling Krylov subspaces for sequences of linear systems, SIAM J. Sci. Comput., Volume 28 (2006) no. 5, pp. 1651-1674 (electronic) | DOI | MR | Zbl

[25] Y. Saad Analysis of augmented Krylov subspace methods, SIAM J. Matrix Anal. Appl., Volume 18 (1997) no. 2, pp. 435-449 | DOI | MR | Zbl

[26] A. Chapman; Y. Saad Deflated and augmented Krylov subspace techniques, Numer. Linear Algebra Appl., Volume 4 (1997) no. 1, pp. 43-66 | DOI | MR | Zbl

[27] V. Dolean; P. Jolivet; F. Nataf An Introduction to Domain Decomposition Methods: Algorithms, Theory and Parallel Implementation, SIAM, Philadelphia, PA, 2015 | DOI

[28] J. Mandel Balancing domain decomposition, Commun. Appl. Numer. Methods, Volume 9 (1992), pp. 233-241 | DOI

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

[30] P. Gosselet; D. Rixen; F.-X. Roux; N. Spillane Simultaneous FETI and block FETI: Robust domain decomposition with multiple search directions, Int. J. Numer. Methods Eng., Volume 104 (2015) no. 10, pp. 905-927 | DOI | MR | Zbl

[31] R. Haferssas; P. Jolivet; F. 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 | MR | Zbl

[32] F. Nataf Mathematical analysis of robustness of two-level domain decomposition methods with respect to inexact coarse solves, Numer. Math., Volume 144 (2020), pp. 811-833 | DOI | MR | Zbl

[33] P. Marchand; X. Claeys; P. Jolivet; F. Nataf; P.-H. Tournier Two-level preconditioning for the h-version boundary element approximation of hypersingular operator with GenEO, Numer. Math., Volume 146 (2020) no. 3, pp. 597-628 | DOI | MR | Zbl

[34] C. Ma; R. Scheichl; T. Dodwell Novel design and analysis of generalized finite element methods based on locally optimal spectral approximations, SIAM J. Numer. Anal., Volume 60 (2022) no. 1, pp. 244-273 | DOI | MR

[35] N. Bootland; V. Dolean; F. Nataf; P.-H. Tournier Two-level DDM preconditioners for positive Maxwell equations, 2020 (preprint) | arXiv

[36] H. Al Daas; P. Jolivet; J. A. Scott A robust algebraic domain decomposition preconditioner for sparse normal equations, SIAM J. Sci. Comput., Volume 44 (2022) no. 3, p. A1047-A1068 | DOI | MR | Zbl

[37] L. Gouarin; N. Spillane Fully algebraic domain decomposition preconditioners with adaptive spectral bounds, 2021 (preprint) | arXiv

[38] F. Nataf; P.-H. Tournier A GenEO domain decomposition method for saddle point problems, 2021 (preprint) | arXiv

[39] J. 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

[40] A. 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

[41] L. F. Pavarino; O. 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

[42] A. Toselli; O. Widlund Domain Decomposition Methods—Algorithms and Theory, Springer Series in Computational Mathematics, 34, Springer, Berlin, Heidelberg, 2005 | DOI

[43] R. Haferssas; P. Jolivet; F. 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 | MR | Zbl

[44] O. Widlund; S. Zampini; S. Scacchi; L. 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 | MR | Zbl

[45] X. Tu; J. 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 | DOI | MR | Zbl

[46] M. F. Murphy; G. H. Golub; A. 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

[47] M. Benzi; G. H. Golub; J. Liesen Numerical solution of saddle point problems, Acta Numer., Volume 14 (2005), pp. 1-137 | DOI | MR | Zbl

[48] E. de Sturler; J. 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

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

[50] M. Benzi; A. J. Wathen Some preconditioning techniques for saddle point problems, Model Order Reduction: Theory, Research Aspects and Applications (Mathematics in Industry), Volume 13, Springer, Berlin, 2008, pp. 195-211 | DOI | MR | Zbl

[51] Y. Notay Convergence of some iterative methods for symmetric saddle point linear systems, SIMAX, Volume 40 (2019), pp. 122-146 | DOI | MR | Zbl

[52] P. Jolivet; F. Nataf HPDDM: High-Performance Unified framework for Domain Decomposition methods, MPI-C++ library, 2014 https://github.com/hpddm/hpddm

[53] F. Hecht New development in FreeFem++, J. Numer. Math., Volume 20 (2012) no. 3–4, pp. 251-265 | MR | Zbl

[54] S. Balay; W. D. Gropp; L. C. McInnes; B. F. Smith Efficient management of parallelism in object oriented numerical software libraries, Modern Software Tools in Scientific Computing (E. Arge; A. M. Bruaset; H. P. Langtangen, eds.), Birkhäuser Press, Boston, MA, 1997, pp. 163-202 | DOI | Zbl

[55] P.-H. Tournier; F. Nataf FFDDM: FreeFem domain decomposition method, 2019 https://doc.freefem.org/documentation/ffddm/index.html

[56] R. Butler; T. Dodwell; A. Reinarz; A. Sandhu; R. Scheichl; L. Seelinger High-performance dune modules for solving large-scale, strongly anisotropic elliptic problems with applications to aerospace composites, Comput. Phys. Commun., Volume 249 (2020), 106997 | DOI | MR

[57] P. Bastian; F. Heimann; S. Marnach Generic implementation of finite element methods in the distributed and unified numerics environment (DUNE), Kybernetika, Volume 46 (2010) no. 2, pp. 294-315 | MR | Zbl

[58] F. Rathgeber; D. A. Ham; L. Mitchell; M. Lange; F. Luporini; A. T. McRae; G.-T. Bercea; G. R. Markall; P. H. Kelly Firedrake: automating the finite element method by composing abstractions, ACM Trans. Math. Softw. (TOMS), Volume 43 (2016) no. 3, pp. 1-27 | DOI | MR | Zbl

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

[60] P. Jenny; S. H. Lee; H. 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 | Zbl

Cited by Sources:

Comments - Policy