BDDC Algorithms with deluxe scaling and adaptive selection of primal constraints for Raviart-Thomas vector fields

Oh, Duk-Soon; Widlund, Olof; Zampini, Stefano; Dohrmann, Clark

doi:10.1090/mcom/3254

BDDC Algorithms with deluxe scaling and adaptive selection of primal constraints for Raviart-Thomas vector fields
HTML articles powered by AMS MathViewer

by Duk-Soon Oh, Olof B. Widlund, Stefano Zampini and Clark R. Dohrmann PDF

Math. Comp. 87 (2018), 659-692 Request permission

Abstract:

A BDDC domain decomposition preconditioner is defined by a coarse component, expressed in terms of primal constraints, a weighted average across the interface between the subdomains, and local components given in terms of solvers of local subdomain problems. BDDC methods for vector field problems discretized with Raviart-Thomas finite elements are introduced. The methods are based on a deluxe type of weighted average and an adaptive selection of primal constraints developed to deal with coefficients with high contrast even inside individual subdomains. For problems with very many subdomains, a third level of the preconditioner is introduced.

Under the assumption that the subdomains are all built from elements of a coarse triangulation of the given domain, that the meshes of each subdomain are quasi uniform and that the material parameters are constant in each subdomain, a bound is obtained for the condition number of the preconditioned linear system which is independent of the values and the jumps of these parameters across the interface between the subdomains as well as the number of subdomains. Numerical experiments, using the PETSc library, are also presented which support the theory and show the effectiveness of the algorithms even for problems not covered by the theory. Included are also experiments with Brezzi-Douglas-Marini finite element approximations.

References

SPE Comparative Solution Projects, http://www.spe.org/web/csp/datasets/set02.htm.
Patrick R. Amestoy, Iain S. Duff, Jean-Yves L’Excellent, and Jacko Koster, A fully asynchronous multifrontal solver using distributed dynamic scheduling, SIAM J. Matrix Anal. Appl. 23 (2001), no. 1, 15–41. MR 1856597, DOI 10.1137/S0895479899358194
E. Anderson, Z. Bai, C. Bischof, S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, and D. Sorensen, LAPACK Users’ Guide, third ed., Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999.
W. N. Anderson Jr. and G. E. Trapp, Shorted operators. II, SIAM J. Appl. Math. 28 (1975), 60–71. MR 356949, DOI 10.1137/0128007
W. N. Anderson Jr. and R. J. Duffin, Series and parallel addition of matrices, J. Math. Anal. Appl. 26 (1969), 576–594. MR 242573, DOI 10.1016/0022-247X(69)90200-5
Douglas N. Arnold, Richard S. Falk, and Ragnar Winther, Preconditioning discrete approximations of the Reissner-Mindlin plate model, RAIRO Modél. Math. Anal. Numér. 31 (1997), no. 4, 517–557 (English, with English and French summaries). MR 1457459, DOI 10.1051/m2an/1997310405171
Douglas N. Arnold, Richard S. Falk, and R. Winther, Preconditioning in $H(\textrm {div})$ and applications, Math. Comp. 66 (1997), no. 219, 957–984. MR 1401938, DOI 10.1090/S0025-5718-97-00826-0
Douglas N. Arnold, Richard S. Falk, and Ragnar Winther, Multigrid in $H(\textrm {div})$ and $H(\textrm {curl})$, Numer. Math. 85 (2000), no. 2, 197–217. MR 1754719, DOI 10.1007/PL00005386
S. Balay, S. Abhyankar, M. F. Adams, J. Brown, P. Brune, K. Buschelman, L. Dalcin, V. Eijkhout, W. D. Gropp, D. Kaushik, M. G. Knepley, L. C. McInnes, K. Rupp, B. F. Smith, S. Zampini, and H. Zhang, PETSc Web page, http://www.mcs.anl.gov/petsc, 2015.
L. Beirão da Veiga, C. Chinosi, C. Lovadina, and L. F. Pavarino, Robust BDDC preconditioners for Reissner-Mindlin plate bending problems and MITC elements, SIAM J. Numer. Anal. 47 (2010), no. 6, 4214–4238. MR 2585185, DOI 10.1137/080717729
L. Beirão da Veiga, D. Cho, L. F. Pavarino, and S. Scacchi, BDDC preconditioners for isogeometric analysis, Math. Models Methods Appl. Sci. 23 (2013), no. 6, 1099–1142. MR 3037302, DOI 10.1142/S0218202513500048
L. Beirão da Veiga, L. F. Pavarino, S. Scacchi, O. B. Widlund, and S. Zampini, Isogeometric BDDC preconditioners with deluxe scaling, SIAM J. Sci. Comput. 36 (2014), no. 3, A1118–A1139. MR 3216651, DOI 10.1137/130917399
L. Beirão da Veiga, L. F. Pavarino, S. Scacchi, O. B. Widlund, and S. Zampini, Adaptive selection of primal constraints for isogeometric BDDC deluxe preconditioners, SIAM J. Sci. Comput. 39 (2017), no. 1, A281–A302. MR 3612901, DOI 10.1137/15M1054675
Dietrich Braess, Finite elements, 3rd ed., Cambridge University Press, Cambridge, 2007. Theory, fast solvers, and applications in elasticity theory; Translated from the German by Larry L. Schumaker. MR 2322235, DOI 10.1017/CBO9780511618635
Susanne C. Brenner and Li-Yeng Sung, BDDC and FETI-DP without matrices or vectors, Comput. Methods Appl. Mech. Engrg. 196 (2007), no. 8, 1429–1435. MR 2277027, DOI 10.1016/j.cma.2006.03.012
Franco Brezzi and Michel Fortin, Mixed and hybrid finite element methods, Springer Series in Computational Mathematics, vol. 15, Springer-Verlag, New York, 1991. MR 1115205, DOI 10.1007/978-1-4612-3172-1
Z. Cai, R. Lazarov, T. A. Manteuffel, and S. F. McCormick, First-order system least squares for second-order partial differential equations. I, SIAM J. Numer. Anal. 31 (1994), no. 6, 1785–1799. MR 1302685, DOI 10.1137/0731091
Juan G. Calvo, A two-level overlapping Schwarz method for $H(\rm curl)$ in two dimensions with irregular subdomains, Electron. Trans. Numer. Anal. 44 (2015), 497–521. MR 3407231
Juan G. Calvo, A BDDC algorithm with deluxe scaling for $H(\textrm {curl})$ in two dimensions with irregular subdomains, Math. Comp. 85 (2016), no. 299, 1085–1111. MR 3454359, DOI 10.1090/mcom/3028
Juan G. Calvo and Olof B. Widlund, An adaptive choice of primal constraints for BDDC domain decomposition algorithms, Electron. Trans. Numer. Anal. 45 (2016), 524–544. MR 3582898
Clark R. Dohrmann, A preconditioner for substructuring based on constrained energy minimization, SIAM J. Sci. Comput. 25 (2003), no. 1, 246–258. MR 2047204, DOI 10.1137/S1064827502412887
C. R. Dohrmann, An approximate BDDC preconditioner, Numer. Linear Algebra Appl. 14 (2007), no. 2, 149–168. MR 2292301, DOI 10.1002/nla.514
C. R. Dohrmann and C. Pechstein, Constraint and weight selection algorithms for BDDC, Slides for a talk by Dohrmann at DD21 in Rennes, France, June 2012. URL=http://www.numa.uni-linz.ac.at/ clemens/dohrmann-pechstein-dd21-talk.pdf.
Clark R. Dohrmann and Olof B. Widlund, An iterative substructuring algorithm for two-dimensional problems in $H(\textrm {curl})$, SIAM J. Numer. Anal. 50 (2012), no. 3, 1004–1028. MR 2970732, DOI 10.1137/100818145
Clark R. Dohrmann and Olof B. Widlund, Some recent tools and a BDDC algorithm for 3D problems in $H(\textrm {curl})$, Domain decomposition methods in science and engineering XX, Lect. Notes Comput. Sci. Eng., vol. 91, Springer, Heidelberg, 2013, pp. 15–25. MR 3242973, DOI 10.1007/978-3-642-35275-1_{2}
Clark R. Dohrmann and Olof B. Widlund, A BDDC algorithm with deluxe scaling for three-dimensional $H(\textbf {curl})$ problems, Comm. Pure Appl. Math. 69 (2016), no. 4, 745–770. MR 3465088, DOI 10.1002/cpa.21574
Maksymilian Dryja, Juan Galvis, and Marcus Sarkis, BDDC methods for discontinuous Galerkin discretization of elliptic problems, J. Complexity 23 (2007), no. 4-6, 715–739. MR 2372024, DOI 10.1016/j.jco.2007.02.003
Maksymilian Dryja and Olof B. Widlund, Schwarz methods of Neumann-Neumann type for three-dimensional elliptic finite element problems, Comm. Pure Appl. Math. 48 (1995), no. 2, 121–155. MR 1319698, DOI 10.1002/cpa.3160480203
Charbel Farhat, Michel Lesoinne, Patrick LeTallec, Kendall Pierson, and Daniel Rixen, FETI-DP: a dual-primal unified FETI method. I. A faster alternative to the two-level FETI method, Internat. J. Numer. Methods Engrg. 50 (2001), no. 7, 1523–1544. MR 1813746, DOI 10.1002/nme.76
Charbel Farhat, Jan Mandel, and François-Xavier Roux, Optimal convergence properties of the FETI domain decomposition method, Comput. Methods Appl. Mech. Engrg. 115 (1994), no. 3-4, 365–385. MR 1285024, DOI 10.1016/0045-7825(94)90068-X
Charbel Farhat, Michel Lesoinne, Patrick LeTallec, Kendall Pierson, and Daniel Rixen, FETI-DP: a dual-primal unified FETI method. I. A faster alternative to the two-level FETI method, Internat. J. Numer. Methods Engrg. 50 (2001), no. 7, 1523–1544. MR 1813746, DOI 10.1002/nme.76
Y. Fragakis and M. Papadrakakis, The mosaic of high performance domain decomposition methods for structural mechanics: Formulation, interrelation and numerical efficiency of primal and dual methods, Comput. Methods Appl. Mech. Engrg 192 (2003), 3799–3830.
Ralf Hiptmair and Andrea Toselli, Overlapping and multilevel Schwarz methods for vector valued elliptic problems in three dimensions, Parallel solution of partial differential equations (Minneapolis, MN, 1997) IMA Vol. Math. Appl., vol. 120, Springer, New York, 2000, pp. 181–208. MR 1838270, DOI 10.1007/978-1-4612-1176-1_{8}
R. Hiptmair, G. Widmer, and J. Zou, Auxiliary space preconditioning in $H_0(\textrm {curl};\ \Omega )$, Numer. Math. 103 (2006), no. 3, 435–459. MR 2221057, DOI 10.1007/s00211-006-0683-0
Ralf Hiptmair and Jinchao Xu, Nodal auxiliary space preconditioning in $\textbf {H}(\textbf {curl})$ and $\textbf {H}(\textrm {div})$ spaces, SIAM J. Numer. Anal. 45 (2007), no. 6, 2483–2509. MR 2361899, DOI 10.1137/060660588
R. Hiptmair, Multigrid method for Maxwell’s equations, SIAM J. Numer. Anal. 36 (1999), no. 1, 204–225. MR 1654571, DOI 10.1137/S0036142997326203
G. Karypis, METIS and ParMETIS, Encyclopedia of Parallel Computing (David Padua, ed.), Springer US, 2011, pp. 1117–1124 (English).
Hyea Hyun Kim and Eric T. Chung, A BDDC algorithm with enriched coarse spaces for two-dimensional elliptic problems with oscillatory and high contrast coefficients, Multiscale Model. Simul. 13 (2015), no. 2, 571–593. MR 3350292, DOI 10.1137/140970598
H. H. Kim, E. T. Chung, and J. Wang, BDDC and FETI-DP algorithms with adaptive coarse spaces for three-dimensional elliptic problems with oscillatory and high contrast coefficients, http://arxiv.org/abs/1606.07560, August 2015.
Axel Klawonn, Patrick Radtke, and Oliver Rheinbach, A comparison of adaptive coarse spaces for iterative substructuring in two dimensions, Electron. Trans. Numer. Anal. 45 (2016), 75–106. MR 3480118
Axel Klawonn and Oliver Rheinbach, Robust FETI-DP methods for heterogeneous three dimensional elasticity problems, Comput. Methods Appl. Mech. Engrg. 196 (2007), no. 8, 1400–1414. MR 2277025, DOI 10.1016/j.cma.2006.03.023
Axel Klawonn, Oliver Rheinbach, and Olof B. Widlund, An analysis of a FETI-DP algorithm on irregular subdomains in the plane, SIAM J. Numer. Anal. 46 (2008), no. 5, 2484–2504. MR 2421044, DOI 10.1137/070688675
Axel Klawonn, Olof B. Widlund, and Maksymilian Dryja, Dual-primal FETI methods for three-dimensional elliptic problems with heterogeneous coefficients, SIAM J. Numer. Anal. 40 (2002), no. 1, 159–179. MR 1921914, DOI 10.1137/S0036142901388081
Tzanio V. Kolev and Panayot S. Vassilevski, Parallel auxiliary space AMG solver for $H(\textrm {div})$ problems, SIAM J. Sci. Comput. 34 (2012), no. 6, A3079–A3098. MR 3029843, DOI 10.1137/110859361
Johannes Kraus, Raytcho Lazarov, Maria Lymbery, Svetozar Margenov, and Ludmil Zikatanov, Preconditioning heterogeneous $H(\textrm {div})$ problems by additive Schur complement approximation and applications, SIAM J. Sci. Comput. 38 (2016), no. 2, A875–A898. MR 3474851, DOI 10.1137/140974092
Patrick Le Tallec, Domain decomposition methods in computational mechanics, Comput. Mech. Adv. 1 (1994), no. 2, 121–220. MR 1263805
Jong Ho Lee, A balancing domain decomposition by constraints deluxe method for Reissner-Mindlin plates with Falk-Tu elements, SIAM J. Numer. Anal. 53 (2015), no. 1, 63–81. MR 3296615, DOI 10.1137/130940669
Jing Li and Xuemin Tu, Convergence analysis of a balancing domain decomposition method for solving a class of indefinite linear systems, Numer. Linear Algebra Appl. 16 (2009), no. 9, 745–773. MR 2554500, DOI 10.1002/nla.639
Jing Li and Olof Widlund, BDDC algorithms for incompressible Stokes equations, SIAM J. Numer. Anal. 44 (2006), no. 6, 2432–2455. MR 2272601, DOI 10.1137/050628556
Jing Li and Olof B. Widlund, FETI-DP, BDDC, and block Cholesky methods, Internat. J. Numer. Methods Engrg. 66 (2006), no. 2, 250–271. MR 2224479, DOI 10.1002/nme.1553
Ping Lin, A sequential regularization method for time-dependent incompressible Navier-Stokes equations, SIAM J. Numer. Anal. 34 (1997), no. 3, 1051–1071. MR 1451113, DOI 10.1137/S0036142994270521
Anders Logg, Kent-Andre Mardal, and Garth N. Wells (eds.), Automated solution of differential equations by the finite element method, Lecture Notes in Computational Science and Engineering, vol. 84, Springer, Heidelberg, 2012. The FEniCS book. MR 3075806, DOI 10.1007/978-3-642-23099-8
Anders Logg and Garth N. Wells, DOLFIN: automated finite element computing, ACM Trans. Math. Software 37 (2010), no. 2, Art. 20, 28. MR 2738227, DOI 10.1145/1731022.1731030
Jan Mandel and Marian Brezina, Balancing domain decomposition for problems with large jumps in coefficients, Math. Comp. 65 (1996), no. 216, 1387–1401. MR 1351204, DOI 10.1090/S0025-5718-96-00757-0
Jan Mandel and Clark R. Dohrmann, Convergence of a balancing domain decomposition by constraints and energy minimization, Numer. Linear Algebra Appl. 10 (2003), no. 7, 639–659. Dedicated to the 70th birthday of Ivo Marek. MR 2030628, DOI 10.1002/nla.341
Jan Mandel, Clark R. Dohrmann, and Radek Tezaur, An algebraic theory for primal and dual substructuring methods by constraints, Appl. Numer. Math. 54 (2005), no. 2, 167–193. MR 2148040, DOI 10.1016/j.apnum.2004.09.022
Jan Mandel and Bedřich Sousedík, Adaptive selection of face coarse degrees of freedom in the BDDC and the FETI-DP iterative substructuring methods, Comput. Methods Appl. Mech. Engrg. 196 (2007), no. 8, 1389–1399. MR 2277024, DOI 10.1016/j.cma.2006.03.010
Jan Mandel, Bedřich Sousedík, and Jakub Šístek, Adaptive BDDC in three dimensions, Math. Comput. Simulation 82 (2012), no. 10, 1812–1831. MR 2967935, DOI 10.1016/j.matcom.2011.03.014
Jan Mandel and Radek Tezaur, On the convergence of a dual-primal substructuring method, Numer. Math. 88 (2001), no. 3, 543–558. MR 1835470, DOI 10.1007/s211-001-8014-1
Peter Monk, Finite element methods for Maxwell’s equations, Numerical Mathematics and Scientific Computation, Oxford University Press, New York, 2003. MR 2059447, DOI 10.1093/acprof:oso/9780198508885.001.0001
J.-C. Nédélec, Mixed finite elements in $\textbf {R}^{3}$, Numer. Math. 35 (1980), no. 3, 315–341. MR 592160, DOI 10.1007/BF01396415
Duk-Soon Oh, Domain Decomposition Methods for Raviart-Thomas Vector Fields, ProQuest LLC, Ann Arbor, MI, 2011. Thesis (Ph.D.)–New York University. MR 2982343
Duk-Soon Oh, An overlapping Schwarz algorithm for Raviart-Thomas vector fields with discontinuous coefficients, SIAM J. Numer. Anal. 51 (2013), no. 1, 297–321. MR 3033012, DOI 10.1137/110838868
D.-S. Oh, A BDDC Preconditioner for Problems Posed in $H(\rm div)$ with Deluxe Scaling, Domain decomposition methods in science and engineering XXII, Lect. Notes Comput. Sci. Eng., vol. 104, Springer, Heidelberg, 2016, pp. 355–361.
Luca F. Pavarino, BDDC and FETI-DP preconditioners for spectral element discretizations, Comput. Methods Appl. Mech. Engrg. 196 (2007), no. 8, 1380–1388. MR 2277023, DOI 10.1016/j.cma.2006.03.009
Luca F. Pavarino, Olof B. Widlund, and Stefano Zampini, BDDC preconditioners for spectral element discretizations of almost incompressible elasticity in three dimensions, SIAM J. Sci. Comput. 32 (2010), no. 6, 3604–3626. MR 2763740, DOI 10.1137/100791701
C. Pechstein and C. R. Dohrmann, Modern domain decomposition methods, BDDC, deluxe scaling, and an algebraic approach., Talk by Pechstein in Linz, Austria. URL: http://people.ricam.oeaw.ac.at/c.pechstein/pechstein-bddc2013.pdf, 2013.
C. Pechstein and C. R. Dohrmann, A Unified Framework for Adaptive BDDC, Tech. Report 2016-20, Johann Radon Institute for Computational and Applied Mathematics (RICAM), 2016, URL:http://www.ricam.oeaw.ac.at/files/reports/16/rep16-20.pdf.
Alfio Quarteroni and Alberto Valli, Numerical approximation of partial differential equations, Springer Series in Computational Mathematics, vol. 23, Springer-Verlag, Berlin, 1994. MR 1299729
Bedřich Sousedík, Nested BDDC for a saddle-point problem, Numer. Math. 125 (2013), no. 4, 761–783. MR 3127330, DOI 10.1007/s00211-013-0548-2
Andrea Toselli, Neumann-Neumann methods for vector field problems, Electron. Trans. Numer. Anal. 11 (2000), 1–24. MR 1749071
Andrea Toselli, Overlapping Schwarz methods for Maxwell’s equations in three dimensions, Numer. Math. 86 (2000), no. 4, 733–752. MR 1794350, DOI 10.1007/PL00005417
Andrea Toselli, Dual-primal FETI algorithms for edge finite-element approximations in 3D, IMA J. Numer. Anal. 26 (2006), no. 1, 96–130. MR 2193972, DOI 10.1093/imanum/dri023
Andrea Toselli and Axel Klawonn, A FETI domain decomposition method for edge element approximations in two dimensions with discontinuous coefficients, SIAM J. Numer. Anal. 39 (2001), no. 3, 932–956. MR 1860451, DOI 10.1137/S0036142999361372
Andrea Toselli and Olof Widlund, Domain decomposition methods—algorithms and theory, Springer Series in Computational Mathematics, vol. 34, Springer-Verlag, Berlin, 2005. MR 2104179, DOI 10.1007/b137868
Xuemin Tu, A BDDC algorithm for a mixed formulation of flow in porous media, Electron. Trans. Numer. Anal. 20 (2005), 164–179. MR 2175341
Xuemin Tu, A BDDC algorithm for flow in porous media with a hybrid finite element discretization, Electron. Trans. Numer. Anal. 26 (2007), 146–160. MR 2366094
Xuemin Tu, Three-level BDDC in three dimensions, SIAM J. Sci. Comput. 29 (2007), no. 4, 1759–1780. MR 2341811, DOI 10.1137/050629902
Xuemin Tu, Three-level BDDC in two dimensions, Internat. J. Numer. Methods Engrg. 69 (2007), no. 1, 33–59. MR 2282536, DOI 10.1002/nme.1753
Xuemin Tu, A three-level BDDC algorithm for a saddle point problem, Numer. Math. 119 (2011), no. 1, 189–217. MR 2824859, DOI 10.1007/s00211-011-0375-2
Xuemin Tu and Jing Li, A balancing domain decomposition method by constraints for advection-diffusion problems, Commun. Appl. Math. Comput. Sci. 3 (2008), 25–60. MR 2425545, DOI 10.2140/camcos.2008.3.25
Panayot S. Vassilevski and Umberto Villa, A mixed formulation for the Brinkman problem, SIAM J. Numer. Anal. 52 (2014), no. 1, 258–281. MR 3162407, DOI 10.1137/120884109
O. B. Widlund and C. R. Dohrmann, BDDC Deluxe Domain Decomposition, Domain decomposition methods in science and engineering XXII, Lect. Notes Comput. Sci. Eng., vol. 104, Springer, Heidelberg, 2016, pp. 93–103.
Barbara I. Wohlmuth, Discretization methods and iterative solvers based on domain decomposition, Lecture Notes in Computational Science and Engineering, vol. 17, Springer-Verlag, Berlin, 2001. MR 1820470, DOI 10.1007/978-3-642-56767-4
Barbara I. Wohlmuth, Andrea Toselli, and Olof B. Widlund, An iterative substructuring method for Raviart-Thomas vector fields in three dimensions, SIAM J. Numer. Anal. 37 (2000), no. 5, 1657–1676. MR 1759911, DOI 10.1137/S0036142998347310
S. Zampini and D. E. Keyes, On the Robustness and Prospects of Adaptive BDDC Methods for Finite Element Discretizations of Elliptic PDES with High-contrast Coefficients, Proceedings of the Platform for Advanced Scientific Computing Conference (New York, NY, USA), PASC ’16, ACM, 2016, pp. 6:1–6:13.
Stefano Zampini, Dual-primal methods for the cardiac bidomain model, Math. Models Methods Appl. Sci. 24 (2014), no. 4, 667–696. MR 3163396, DOI 10.1142/S0218202513500632
S. Zampini, Adaptive BDDC Deluxe Methods for H(curl), Proceedings of the 23rd International Conference on Domain Decomposition Methods, Lecture Notes in Computational Science and Engineering, vol. 116, Springer, 2017, pp. 285–292.
Stefano Zampini, PCBDDC: a class of robust dual-primal methods in PETSc, SIAM J. Sci. Comput. 38 (2016), no. 5, S282–S306. MR 3565564, DOI 10.1137/15M1025785
S. Zampini and X. Tu, Adaptive Multilevel BDDC Deluxe Algorithms for Flow in Porous Media, Tech. report, 2016, submitted.