×

BDDC algorithms with deluxe scaling and adaptive selection of primal constraints for Raviart-Thomas vector fields. (English) Zbl 1380.65065

Summary: 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.

MSC:

65F08 Preconditioners for iterative methods
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
37C10 Dynamics induced by flows and semiflows
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] SPE_Comp SPE Comparative Solution Projects, http://www.spe.org/web/csp/datasets/set02.htm.
[2] Amestoy, Patrick R.; Duff, Iain S.; L’Excellent, Jean-Yves; Koster, Jacko, A fully asynchronous multifrontal solver using distributed dynamic scheduling, SIAM J. Matrix Anal. Appl., 23, 1, 15-41 (2001) · Zbl 0992.65018
[3] LAPACK 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. · Zbl 0934.65030
[4] Anderson, W. N., Jr.; Trapp, G. E., Shorted operators. II, SIAM J. Appl. Math., 28, 60-71 (1975) · Zbl 0295.47032
[5] Anderson, W. N., Jr.; Duffin, R. J., Series and parallel addition of matrices, J. Math. Anal. Appl., 26, 576-594 (1969) · Zbl 0177.04904
[6] Arnold, Douglas N.; Falk, Richard S.; Winther, Ragnar, Preconditioning discrete approximations of the Reissner-Mindlin plate model, RAIRO Mod\'el. Math. Anal. Num\'er., 31, 4, 517-557 (1997) · Zbl 0877.73060
[7] Arnold, Douglas N.; Falk, Richard S.; Winther, R., Preconditioning in \(H({\rm div})\) and applications, Math. Comp., 66, 219, 957-984 (1997) · Zbl 0870.65112
[8] Arnold, Douglas N.; Falk, Richard S.; Winther, Ragnar, Multigrid in \(H({\rm div})\) and \(H({\rm curl})\), Numer. Math., 85, 2, 197-217 (2000) · Zbl 0974.65113
[9] petsc-web-page 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.
[10] Beir\~ao da Veiga, L.; Chinosi, C.; Lovadina, C.; Pavarino, L. F., Robust BDDC preconditioners for Reissner-Mindlin plate bending problems and MITC elements, SIAM J. Numer. Anal., 47, 6, 4214-4238 (2010) · Zbl 1252.74062
[11] Beir\~ao da Veiga, L.; Cho, D.; Pavarino, L. F.; Scacchi, S., BDDC preconditioners for isogeometric analysis, Math. Models Methods Appl. Sci., 23, 6, 1099-1142 (2013) · Zbl 1280.65138
[12] MR3216651 L. Beir\~ao 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. · Zbl 1320.65047
[13] Beir\~ao da Veiga, L.; Pavarino, L. F.; Scacchi, S.; Widlund, O. B.; Zampini, S., Adaptive selection of primal constraints for isogeometric BDDC deluxe preconditioners, SIAM J. Sci. Comput., 39, 1, A281-A302 (2017) · Zbl 1360.65090
[14] Braess, Dietrich, Finite elements, xviii+365 pp. (2007), Cambridge University Press, Cambridge · Zbl 1118.65117
[15] Brenner, Susanne C.; Sung, Li-Yeng, BDDC and FETI-DP without matrices or vectors, Comput. Methods Appl. Mech. Engrg., 196, 8, 1429-1435 (2007) · Zbl 1173.65363
[16] Brezzi, Franco; Fortin, Michel, Mixed and Hybrid Finite Element Methods, Springer Series in Computational Mathematics 15, x+350 pp. (1991), Springer-Verlag, New York · Zbl 0788.73002
[17] Cai, Z.; Lazarov, R.; Manteuffel, T. A.; McCormick, S. F., First-order system least squares for second-order partial differential equations. I, SIAM J. Numer. Anal., 31, 6, 1785-1799 (1994) · Zbl 0813.65119
[18] Calvo, J. G., A two-level overlapping Schwarz method for \(H(\rm curl)\) in two dimensions with irregular subdomains, Electron. Trans. Numer. Anal., 44, 497-521 (2015) · Zbl 1330.65175
[19] Calvo, Juan G., A BDDC algorithm with deluxe scaling for \(H({\rm curl})\) in two dimensions with irregular subdomains, Math. Comp., 85, 299, 1085-1111 (2016) · Zbl 1332.65178
[20] Calvo, Juan G.; Widlund, Olof B., An adaptive choice of primal constraints for BDDC domain decomposition algorithms, Electron. Trans. Numer. Anal., 45, 524-544 (2016) · Zbl 1357.65295
[21] Dohrmann, Clark R., A preconditioner for substructuring based on constrained energy minimization, SIAM J. Sci. Comput., 25, 1, 246-258 (2003) · Zbl 1038.65039
[22] Dohrmann, C. R., An approximate BDDC preconditioner, Numer. Linear Algebra Appl., 14, 2, 149-168 (2007) · Zbl 1199.65088
[23] dohrmann_rennes 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.
[24] Dohrmann, Clark R.; Widlund, Olof B., An iterative substructuring algorithm for two-dimensional problems in \(H({\rm curl})\), SIAM J. Numer. Anal., 50, 3, 1004-1028 (2012) · Zbl 1260.78014
[25] MR3242973 C. R. Dohrmann and O. B. Widlund, Some recent tools and a BDDC algorithm for 3D problems in \(H(curl)\), Domain decomposition methods in science and engineering XX, Lect. Notes Comput. Sci. Eng., vol. 91, Springer, Heidelberg, 2013, pp. 15-25.
[26] Dohrmann, Clark R.; Widlund, Olof B., A BDDC algorithm with deluxe scaling for three-dimensional \(H({\bf curl})\) problems, Comm. Pure Appl. Math., 69, 4, 745-770 (2016) · Zbl 1343.65136
[27] Dryja, Maksymilian; Galvis, Juan; Sarkis, Marcus, BDDC methods for discontinuous Galerkin discretization of elliptic problems, J. Complexity, 23, 4-6, 715-739 (2007) · Zbl 1133.65097
[28] Dryja, Maksymilian; Widlund, Olof B., Schwarz methods of Neumann-Neumann type for three-dimensional elliptic finite element problems, Comm. Pure Appl. Math., 48, 2, 121-155 (1995) · Zbl 0824.65106
[29] Farhat, Charbel; Lesoinne, Michel; LeTallec, Patrick; Pierson, Kendall; Rixen, Daniel, FETI-DP: a dual-primal unified FETI method. I. A faster alternative to the two-level FETI method, Internat. J. Numer. Methods Engrg., 50, 7, 1523-1544 (2001) · Zbl 1008.74076
[30] Farhat, Charbel; Mandel, Jan; Roux, Fran\c{c}ois-Xavier, Optimal convergence properties of the FETI domain decomposition method, Comput. Methods Appl. Mech. Engrg., 115, 3-4, 365-385 (1994)
[31] Farhat_Roux C. Farhat and F.-X. Roux, A method of finite element tearing and interconnecting its parallel solution algorithm, Internat. J. Numer. Methods Engrg. 32 (1991), 1205-1227. · Zbl 0758.65075
[32] Fragakis03themosaic 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. · Zbl 1054.74069
[33] Hiptmair, Ralf; Toselli, Andrea, 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. 120, 181-208 (2000), Springer, New York · Zbl 0961.65109
[34] Hiptmair, R.; Widmer, G.; Zou, J., Auxiliary space preconditioning in \(H_0({\rm curl};\ \Omega )\), Numer. Math., 103, 3, 435-459 (2006) · Zbl 1094.65118
[35] Hiptmair, Ralf; Xu, Jinchao, Nodal auxiliary space preconditioning in \({\bf H}({\bf curl})\) and \({\bf H}({\rm div})\) spaces, SIAM J. Numer. Anal., 45, 6, 2483-2509 (2007) · Zbl 1153.78006
[36] Hiptmair, R., Multigrid method for Maxwell’s equations, SIAM J. Numer. Anal., 36, 1, 204-225 (1999) · Zbl 0922.65081
[37] ParMETIS G. Karypis, METIS and ParMETIS, Encyclopedia of Parallel Computing (David Padua, ed.), Springer US, 2011, pp. 1117-1124 (English).
[38] Kim, Hyea Hyun; Chung, Eric T., A BDDC algorithm with enriched coarse spaces for two-dimensional elliptic problems with oscillatory and high contrast coefficients, Multiscale Model. Simul., 13, 2, 571-593 (2015) · Zbl 1317.65090
[39] chung_kim_2015 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. · Zbl 1380.65374
[40] Klawonn, Axel; Radtke, Patrick; Rheinbach, Oliver, A comparison of adaptive coarse spaces for iterative substructuring in two dimensions, Electron. Trans. Numer. Anal., 45, 75-106 (2016) · Zbl 1338.65084
[41] Klawonn, Axel; Rheinbach, Oliver, Robust FETI-DP methods for heterogeneous three dimensional elasticity problems, Comput. Methods Appl. Mech. Engrg., 196, 8, 1400-1414 (2007) · Zbl 1173.74428
[42] Klawonn, Axel; Rheinbach, Oliver; Widlund, Olof B., An analysis of a FETI-DP algorithm on irregular subdomains in the plane, SIAM J. Numer. Anal., 46, 5, 2484-2504 (2008) · Zbl 1176.65135
[43] Klawonn, Axel; Widlund, Olof B.; Dryja, Maksymilian, Dual-primal FETI methods for three-dimensional elliptic problems with heterogeneous coefficients, SIAM J. Numer. Anal., 40, 1, 159-179 (2002) · Zbl 1032.65031
[44] Kolev, Tzanio V.; Vassilevski, Panayot S., Parallel auxiliary space AMG solver for \(H({\rm div})\) problems, SIAM J. Sci. Comput., 34, 6, A3079-A3098 (2012) · Zbl 1332.65042
[45] Kraus, Johannes; Lazarov, Raytcho; Lymbery, Maria; Margenov, Svetozar; Zikatanov, Ludmil, Preconditioning heterogeneous \(H({\rm div})\) problems by additive Schur complement approximation and applications, SIAM J. Sci. Comput., 38, 2, A875-A898 (2016) · Zbl 1380.65376
[46] Le Tallec, Patrick, Domain decomposition methods in computational mechanics, Comput. Mech. Adv., 1, 2, 121-220 (1994) · Zbl 0802.73079
[47] Lee, Jong Ho, A balancing domain decomposition by constraints deluxe method for Reissner-Mindlin plates with Falk-Tu elements, SIAM J. Numer. Anal., 53, 1, 63-81 (2015) · Zbl 1327.65263
[48] Li, Jing; Tu, Xuemin, Convergence analysis of a balancing domain decomposition method for solving a class of indefinite linear systems, Numer. Linear Algebra Appl., 16, 9, 745-773 (2009) · Zbl 1224.65248
[49] Li, Jing; Widlund, Olof, BDDC algorithms for incompressible Stokes equations, SIAM J. Numer. Anal., 44, 6, 2432-2455 (2006) · Zbl 1233.76077
[50] Li, Jing; Widlund, Olof B., FETI-DP, BDDC, and block Cholesky methods, Internat. J. Numer. Methods Engrg., 66, 2, 250-271 (2006) · Zbl 1114.65142
[51] Lin, Ping, A sequential regularization method for time-dependent incompressible Navier-Stokes equations, SIAM J. Numer. Anal., 34, 3, 1051-1071 (1997) · Zbl 0882.76018
[52] Automated Solution of Differential Equations by the Finite Element Method, Lecture Notes in Computational Science and Engineering 84, xiv+723 pp. (2012), Springer, Heidelberg · Zbl 1247.65105
[53] Logg, Anders; Wells, Garth N., DOLFIN: automated finite element computing, ACM Trans. Math. Software, 37, 2, Art. 20, 28 pp. (2010) · Zbl 1364.65254
[54] Mandel, Jan; Brezina, Marian, Balancing domain decomposition for problems with large jumps in coefficients, Math. Comp., 65, 216, 1387-1401 (1996) · Zbl 0853.65129
[55] Mandel, Jan; Dohrmann, Clark R., Convergence of a balancing domain decomposition by constraints and energy minimization, Numer. Linear Algebra Appl., 10, 7, 639-659 (2003) · Zbl 1071.65558
[56] Mandel, Jan; Dohrmann, Clark R.; Tezaur, Radek, An algebraic theory for primal and dual substructuring methods by constraints, Appl. Numer. Math., 54, 2, 167-193 (2005) · Zbl 1076.65100
[57] Mandel, Jan; Soused\'\i k, Bed\v rich, Adaptive selection of face coarse degrees of freedom in the BDDC and the FETI-DP iterative substructuring methods, Comput. Methods Appl. Mech. Engrg., 196, 8, 1389-1399 (2007) · Zbl 1173.74435
[58] Mandel, Jan; Soused\'\i k, Bed\v rich; \v S\'\i stek, Jakub, Adaptive BDDC in three dimensions, Math. Comput. Simulation, 82, 10, 1812-1831 (2012) · Zbl 1255.65225
[59] Mandel, Jan; Tezaur, Radek, On the convergence of a dual-primal substructuring method, Numer. Math., 88, 3, 543-558 (2001) · Zbl 1003.65126
[60] Monk, Peter, Finite Element Methods for Maxwell’s Equations, Numerical Mathematics and Scientific Computation, xiv+450 pp. (2003), Oxford University Press, New York · Zbl 1024.78009
[61] N\'ed\'elec, J.-C., Mixed finite elements in \({\bf R}^3\), Numer. Math., 35, 3, 315-341 (1980) · Zbl 0419.65069
[62] Oh, Duk-Soon, Domain Decomposition Methods for Raviart-Thomas Vector Fields, 128 pp. (2011), ProQuest LLC, Ann Arbor, MI
[63] Oh, Duk-Soon, An overlapping Schwarz algorithm for Raviart-Thomas vector fields with discontinuous coefficients, SIAM J. Numer. Anal., 51, 1, 297-321 (2013) · Zbl 1267.65196
[64] Oh_DD22 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.
[65] Pavarino, Luca F., BDDC and FETI-DP preconditioners for spectral element discretizations, Comput. Methods Appl. Mech. Engrg., 196, 8, 1380-1388 (2007) · Zbl 1173.65359
[66] Pavarino, Luca F.; Widlund, Olof B.; Zampini, Stefano, BDDC preconditioners for spectral element discretizations of almost incompressible elasticity in three dimensions, SIAM J. Sci. Comput., 32, 6, 3604-3626 (2010) · Zbl 1278.74058
[67] pechstein_dohrmann 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.
[68] pechstein_dohrmann_TR 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. · Zbl 1368.65043
[69] Quarteroni, Alfio; Valli, Alberto, Numerical Approximation of Partial Differential Equations, Springer Series in Computational Mathematics 23, xvi+543 pp. (1994), Springer-Verlag, Berlin · Zbl 0803.65088
[70] Soused\'\i k, Bed\v rich, Nested BDDC for a saddle-point problem, Numer. Math., 125, 4, 761-783 (2013) · Zbl 1282.65167
[71] Toselli, Andrea, Neumann-Neumann methods for vector field problems, Electron. Trans. Numer. Anal., 11, 1-24 (2000) · Zbl 0951.65117
[72] Toselli, Andrea, Overlapping Schwarz methods for Maxwell’s equations in three dimensions, Numer. Math., 86, 4, 733-752 (2000) · Zbl 0980.78010
[73] Toselli, Andrea, Dual-primal FETI algorithms for edge finite-element approximations in 3D, IMA J. Numer. Anal., 26, 1, 96-130 (2006) · Zbl 1088.65102
[74] Toselli, Andrea; Klawonn, Axel, A FETI domain decomposition method for edge element approximations in two dimensions with discontinuous coefficients, SIAM J. Numer. Anal., 39, 3, 932-956 (2001) · Zbl 1001.65124
[75] Toselli, Andrea; Widlund, Olof, Domain Decomposition Methods-Algorithms and Theory, Springer Series in Computational Mathematics 34, xvi+450 pp. (2005), Springer-Verlag, Berlin · Zbl 1069.65138
[76] Tu, Xuemin, A BDDC algorithm for a mixed formulation of flow in porous media, Electron. Trans. Numer. Anal., 20, 164-179 (2005) · Zbl 1160.76368
[77] Tu, Xuemin, A BDDC algorithm for flow in porous media with a hybrid finite element discretization, Electron. Trans. Numer. Anal., 26, 146-160 (2007) · Zbl 1170.76034
[78] Tu, Xuemin, Three-level BDDC in three dimensions, SIAM J. Sci. Comput., 29, 4, 1759-1780 (2007) · Zbl 1163.65094
[79] Tu, Xuemin, Three-level BDDC in two dimensions, Internat. J. Numer. Methods Engrg., 69, 1, 33-59 (2007) · Zbl 1134.65087
[80] Tu, Xuemin, A three-level BDDC algorithm for a saddle point problem, Numer. Math., 119, 1, 189-217 (2011) · Zbl 1230.65136
[81] Tu, Xuemin; Li, Jing, A balancing domain decomposition method by constraints for advection-diffusion problems, Commun. Appl. Math. Comput. Sci., 3, 25-60 (2008) · Zbl 1165.65402
[82] Vassilevski, Panayot S.; Villa, Umberto, A mixed formulation for the Brinkman problem, SIAM J. Numer. Anal., 52, 1, 258-281 (2014) · Zbl 1457.65219
[83] widlund:2014:DD22 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. · Zbl 1339.65242
[84] Wohlmuth, Barbara I., Discretization Methods and Iterative Solvers Based on Domain Decomposition, Lecture Notes in Computational Science and Engineering 17, x+197 pp. (2001), Springer-Verlag, Berlin · Zbl 0966.65097
[85] Wohlmuth, Barbara I.; Toselli, Andrea; Widlund, Olof B., An iterative substructuring method for Raviart-Thomas vector fields in three dimensions, SIAM J. Numer. Anal., 37, 5, 1657-1676 (2000) · Zbl 0956.65115
[86] Zampini:2016:RPA:2929908.2929919 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.
[87] Zampini, Stefano, Dual-primal methods for the cardiac bidomain model, Math. Models Methods Appl. Sci., 24, 4, 667-696 (2014) · Zbl 1291.92007
[88] Zampini_DD23 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. · Zbl 1371.78318
[89] Zampini, Stefano, PCBDDC: a class of robust dual-primal methods in PETSc, SIAM J. Sci. Comput., 38, 5, S282-S306 (2016) · Zbl 1352.65632
[90] zampini_tu:2016 S. Zampini and X. Tu, Adaptive Multilevel BDDC Deluxe Algorithms for Flow in Porous Media, Tech. report, 2016, submitted. · Zbl 1426.76582
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.