×

Two-level overlapping Schwarz methods based on local generalized eigenproblems for Hermitian variational problems. (English) Zbl 1492.65345

Summary: The research of the two-level overlapping Schwarz (TL-OS) methods based on constrained energy minimizing coarse space is still in its infancy, and there exist some defects, e.g., mainly for a second order elliptic problem and too heavy computational cost of coarse space construction. In this paper, by introducing appropriate assumptions, we propose more concise coarse basis functions for general Hermitian positive and definite discrete systems, and establish the algorithmic and theoretical frameworks of the corresponding TL-OS methods. Furthermore, to enhance the practicability of the algorithm, we design two economical TL-OS preconditioners and prove the condition number estimate. As the first application of the frameworks, we prove that the assumptions hold for the linear finite element discretization of a second order elliptic problem with high contrast and oscillatory coefficient and the condition number of the TL-OS preconditioned system is robust with respect to the model and mesh parameters. In particular, we also prove that the condition number of the economically preconditioned system is independent of the jump range under a certain jump distribution. Experimental results show that the first kind of economical preconditioner is more efficient and stable than the existing one. Second, we construct TL-OS and the economical TL-OS preconditioners for the plane wave least squares discrete system of the Helmholtz equation by using the frameworks. The numerical results for homogeneous and nonhomogeneous cases illustrate that the preconditioned conjugate gradient method based on the proposed preconditioners has good stability in terms of the angular frequency, mesh parameters, and the number of degrees of freedom in each element.

MSC:

65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
65F10 Iterative numerical methods for linear systems
15B57 Hermitian, skew-Hermitian, and related matrices
65F08 Preconditioners for iterative methods
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] A. Toselli and O. Widlund, Domain Decomposition Methods: Algorithms and Theory, Springer Ser. Comput. Math. 34, Springer-Verlag, Berlin, 2005. · Zbl 1069.65138
[2] C. Dohrmann, A preconditioner for substructuring based on constrained energy minimization, SIAM J. Sci. Comput., 25 (2003), pp. 246-258, https://doi.org/10.1137/S1064827502412887. · Zbl 1038.65039
[3] J. Mandel and C. Dohrmann, Convergence of a balancing domain decomposition by constraints and energy minimization, Numer. Linear Algebra Appl., 10 (2003), pp. 639-659. · Zbl 1071.65558
[4] J. Li and O. Widlund, BDDC algorithms for incompressible Stokes equations, SIAM J. Numer. Anal., 44 (2006), pp. 2432-2455, https://doi.org/10.1137/050628556. · Zbl 1233.76077
[5] L. Pavarino, O. Widlund, and S. Zampini, BDDC preconditioners for spectral element discretizations of almost incompressible elasticity in three dimensions, SIAM J. Sci. Comput., 32 (2010), pp. 3604-3626, https://doi.org/10.1137/100791701. · Zbl 1278.74058
[6] J. Li and O. B. Widlund, FETI-DP, BDDC, and block Cholesky methods, Internat. J. Numer. Methods Engrg., 66 (2006), pp. 250-271. · Zbl 1114.65142
[7] J. Mandel and B. 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), pp. 1389-1399. · Zbl 1173.74435
[8] J. Mandel, B. Sousedík, and J. Šístek, Adaptive BDDC in three dimensions, Math. Comput. Simulation, 82 (2012), pp. 1812-1831. · Zbl 1255.65225
[9] H. H. Kim and E. 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), pp. 571-593, https://doi.org/10.1137/140970598. · Zbl 1317.65090
[10] A. Klawonn, P. Radtke, and O. Rheinbach, Adaptive coarse spaces for BDDC with a transformation of basis, in Domain Decomposition Methods in Science and Engineering XXII, Lect. Notes Comput. Sci. Eng. 104, Springer, Cham, 2016, pp. 301-309. · Zbl 1339.65238
[11] C. Dohrmann and C. Pechstein, Modern Domain Decomposition Solvers: BDDC, Deluxe Scaling, and an Algebraic Approach, http://people.ricam.oeaw.ac.at/c.pechstein/pechstein-bddc2013.pdf, 2013.
[12] W. Anderson and R. Duffin, Series and parallel addition of matrices, J. Math. Anal. Appl., 26 (1969), pp. 576-594. · Zbl 0177.04904
[13] H. Kim, E. Chung, and J. Wang, BDDC and FETI-DP preconditioners with adaptive coarse spaces for three-dimensional elliptic problems with oscillatory and high contrast coefficients, J. Comput. Phys., 349 (2017), pp. 191-214. · Zbl 1380.65374
[14] H. Kim, E. Chung, and C. Xu, A BDDC algorithm with adaptive primal constraints for staggered discontinuous Galerkin approximation of elliptic problems with highly oscillating coefficients, J. Comput. Appl. Math., 311 (2017), pp. 599-617. · Zbl 1382.65410
[15] D. Oh, O. Widlund, S. Zampini, and C. Dohrmann, BDDC algorithms with deluxe scaling and adaptive selection of primal constraints for Raviart-Thomas vector fields, Math. Comput., 87 (2018), pp. 659-692. · Zbl 1380.65065
[16] S. Zampini and X. Tu, Multilevel balancing domain decomposition by constraints deluxe algorithms with adaptive coarse spaces for flow in porous media, SIAM J. Sci. Comput., 39 (2017), pp. A1389-A1415, https://doi.org/10.1137/16M1080653. · Zbl 1426.76582
[17] J. Peng, J. Wang, and S. Shu, Adaptive BDDC algorithms for the system arising from plane wave discretization of Helmholtz equations, Internat. J. Numer. Methods Engrg., 116 (2018), pp. 683-707.
[18] J. Peng, S. Shu, J. Wang, and L. Zhong, Adaptive-multilevel BDDC algorithm for three-dimensional plane wave Helmholtz systems, J. Comput. Appl. Math., 381 (2021), 113011. · Zbl 1446.65178
[19] C. Pechstein and C. R. Dohrmann, A unified framework for adaptive BDDC, Electron. Trans. Numer. Anal., 46 (2017), pp. 273-336. · Zbl 1368.65043
[20] J. Peng, S. Shu, J. Wang, and L. Zhong, An adaptive BDDC preconditioner for advection-diffusion problems with a stabilized finite element discretization, Appl. Numer. Math., 165 (2021), pp. 184-197. · Zbl 1469.76064
[21] J. Lent, R. Scheichl, and I. Graham, Energy-minimizing coarse spaces for two-level Schwarz methods for multiscale PDEs, Numer. Linear Algebra Appl., 16 (2010), pp. 775-799. · Zbl 1224.65292
[22] J. Galvis, E. Chung, Y. Efendiev, and W. Leung, On overlapping domain decomposition methods for high-contrast multiscale problems, in Domain Decomposition Methods in Science and Engineering XXIV, Lect. Notes Comput. Sci. Eng. 125., Springer, Cham, 2017, pp. 45-57, https://doi.org/10.1007/978-3-319-93873-8_4. · Zbl 1442.65427
[23] J. Wang, E. Chung, and H. Kim, A two-level overlapping Schwarz method with energy-minimizing multiscale coarse basis functions, J. Comput. Appl. Math., 370 (2020), 112600. · Zbl 1493.65267
[24] E. Chung, Y. Efendiev, and W. Leung, Constraint energy minimizing generalized multiscale finite element method, Comput. Methods Appl. Mech. Engrg., 339 (2018), pp. 298-319. · Zbl 1440.65195
[25] R. Hiptmair and J. Xu, Nodal auxiliary space preconditioning in \(H({curl})\) and \(H({div})\) spaces, SIAM J. Numer. Anal., 45 (2007), pp. 2483-2509, https://doi.org/10.1137/060660588. · Zbl 1153.78006
[26] Q. Hu, S. Shu, and J. Wang, Nonoverlapping domain decomposition methods with a simple coarse space for elliptic problems, Math. Comput., 79 (2010), pp. 2059-2078. · Zbl 1204.65140
[27] J. Xu and Y. Zhu, Uniform convergent multigrid methods for elliptic problems with strongly discontinuous coefficients, Math. Models Methods Appl. Sci., 18 (2008), pp. 77-105. · Zbl 1151.65097
[28] Q. Hu and L. Yuan, A weighted variational formulation based on plane wave basis for discretization of Helmholtz equations, Int. J. Numer. Anal. Model., 11 (2014), pp. 587-607. · Zbl 1499.65666
[29] Q. Hu and H. Zhang, Substructuring preconditioners for the systems arising from plane wave discretization of Helmholtz equations, SIAM J. Sci. Comput., 38 (2016), pp. A2232-A2261, https://doi.org/10.1137/151003040. · Zbl 1342.65219
[30] Q. Hu and X. Li, Efficient multilevel preconditioners for three-dimensional plane wave Helmholtz systems with large wave numbers, Multiscale Model. Simul., 15 (2017), pp. 1242-1266, https://doi.org/10.1137/16M1084791.
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.