Analysis of FETI methods for multiscale PDEs. (English) Zbl 1170.65097
This paper is concerned with the convergence of a variant of the finite element tearing and interconnecting (FETI) methods for a model of elliptic problem with highly heterogeneous (multiscale) coefficients \(\alpha(x)\); in particular, \(\alpha\) can have strong variation within subdomains and/or jumps that are not aligned with the subdomain interfaces.
Thanks to a minimisation and cut-off arguments, the authors show rigorously that for an arbitrary (positive) coefficient function \(\alpha \in L^\infty(\Omega)\) the condition number of the preconditioned FETI system can be bounded by \(C(\alpha)(1+\log(H/h))^2\), where \(H\) is the subdomain diameter and \(h\) is the mesh size. In addition to this, the coefficient \(C(\alpha)\) depends only on the coefficient variation in the vicinity of subdomain interfaces. This yields the important particular case when \(\alpha|_{\Omega_i}\) varies only midly in a layer \(\Omega_{i,\eta}\) of width \(\eta\) near the boundary of each of the subdomain \(\Omega_i\), then \(C(\alpha)={\mathcal{O}}((H/\eta)^2)\), independent of the variation of \(\alpha\) in the remainder \(\Omega_i\backslash \Omega_{i,\eta}\) of each subdomain and independent of any jumps of \(\alpha \) across subdomain interfaces. The authors show that this quadratic dependence of \(C(\alpha)\) on \(H/\eta\) can be relaxed to a linear dependence under stronger assumptions on the behavior of \(\alpha\) in the interior of the subdomains. Numerical tests justifying the theoretical results are presented.
Thanks to a minimisation and cut-off arguments, the authors show rigorously that for an arbitrary (positive) coefficient function \(\alpha \in L^\infty(\Omega)\) the condition number of the preconditioned FETI system can be bounded by \(C(\alpha)(1+\log(H/h))^2\), where \(H\) is the subdomain diameter and \(h\) is the mesh size. In addition to this, the coefficient \(C(\alpha)\) depends only on the coefficient variation in the vicinity of subdomain interfaces. This yields the important particular case when \(\alpha|_{\Omega_i}\) varies only midly in a layer \(\Omega_{i,\eta}\) of width \(\eta\) near the boundary of each of the subdomain \(\Omega_i\), then \(C(\alpha)={\mathcal{O}}((H/\eta)^2)\), independent of the variation of \(\alpha\) in the remainder \(\Omega_i\backslash \Omega_{i,\eta}\) of each subdomain and independent of any jumps of \(\alpha \) across subdomain interfaces. The authors show that this quadratic dependence of \(C(\alpha)\) on \(H/\eta\) can be relaxed to a linear dependence under stronger assumptions on the behavior of \(\alpha\) in the interior of the subdomains. Numerical tests justifying the theoretical results are presented.
Reviewer: Abdallah Bradji (Tebessa)
MSC:
| 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 |
Keywords:
finite element tearing and interconnecting methods; multiscale partial differential equations; FETI methods; numerical examples; preconditioning; convergence; elliptic problem; condition numberSoftware:
Total FETIReferences:
| [1] | Aksoylu B., Graham I.G., Klie H., Scheichl R.: Towards a rigorously justified algebraic preconditioner for high-contrast diffusion problems. Comput. Visual. Sci. 11(4–6), 319–331 (2008) · doi:10.1007/s00791-008-0105-1 |
| [2] | Alcouffe R.E., Brandt A., Dendy J.J.E., Painter J.W.: The multi-grid method for the diffusion equation with strongly discontinuous coefficients. SIAM J. Sci. Comput. 2(4), 430–454 (1981) · Zbl 0474.76082 · doi:10.1137/0902035 |
| [3] | Bramble J.H., Pasciak J.E., Schatz A.H.: The construction of preconditioners for elliptic problems by substructuring, IV. Math. Comp. 53(187), 1–24 (1989) · Zbl 0668.65082 |
| [4] | Brenner S.C.: Analysis of two-dimensional FETI-DP preconditioners by the standard additive Schwarz framework. Electron. Trans. Numer. Anal. 16, 165–185 (2003) · Zbl 1065.65136 |
| [5] | Brenner S.C., He Q.: Lower bounds for three-dimensional non-overlapping domain decomposition algorithms. Numer. Math. 93(3), 445–470 (2003) · Zbl 1054.65043 · doi:10.1007/s002110100376 |
| [6] | Chan T.F., Mathew T.: Domain decomposition methods. In Acta Numerica 1994. Cambridge University Press, London (1994) · Zbl 0809.65112 |
| [7] | Cliffe K.A., Graham I.G., Scheichl R., Stals L.: Parallel computation of flow in heterogeneous media modelled by mixed finite elements. J. Comput. Phys. 164(2), 258–282 (2000) · Zbl 0995.76044 · doi:10.1006/jcph.2000.6593 |
| [8] | Dohrmann C.R.: A preconditioner for substructuring based on constrained energy minimization. SIAM J. Sci. Comput. 25(1), 246–258 (2003) · Zbl 1038.65039 · doi:10.1137/S1064827502412887 |
| [9] | Dohrmann C.R., Klawonn A., Widlund O.B.: Domain decomposition for less regular subdomains: overlapping Schwarz in two dimensions. SIAM J. Numer. Anal. 46(4), 2153–2168 (2008) · Zbl 1183.65160 · doi:10.1137/070685841 |
| [10] | Dostál Z., Horák D., Kučera R.: Total FETI: an easier implementable variant of the FETI method for numerical solution of elliptic PDE. Commun. Numer. Methods Eng. 22(12), 1155–1162 (2006) · Zbl 1107.65104 · doi:10.1002/cnm.881 |
| [11] | Evans L.C.: Partial differential equations. Graduate Studies in Mathematics, vol. 19. American Mathematical Society, Providence (1998) · Zbl 0902.35002 |
| [12] | Farhat C., Lesoinne M., Le Tallec P., Pierson K., Rixen D.: FETI-DP: A dual-primal unified FETI method I: a faster alternative to the two-level FETI method. Int. J. Numer. Methods Eng. 50, 1523–1544 (2001) · Zbl 1008.74076 · doi:10.1002/nme.76 |
| [13] | Farhat C., Roux F.-X.: A method of finite element tearing and interconnecting and its parallel solution algorithm. Int. J. Numer. Meth. Eng. 32, 1205–1227 (1991) · Zbl 0758.65075 · doi:10.1002/nme.1620320604 |
| [14] | Graham I.G., Hagger M.J.: Unstructured additive Schwarz-conjugate gradient method for elliptic problems with highly discontinuous coefficients. SIAM J. Sci. Comput. 20(6), 2041–2066 (1999) · Zbl 0943.65147 · doi:10.1137/S1064827596305593 |
| [15] | Graham I.G., Lechner P.O., Scheichl R.: Domain decomposition for multiscale PDEs. Numer. Math. 106(4), 589–626 (2007) · Zbl 1141.65084 · doi:10.1007/s00211-007-0074-1 |
| [16] | Graham I.G., Scheichl R.: Robust domain decomposition algorithms for multiscale PDEs. Numer. Methods Partial Differ. Equ. 23, 859–878 (2007) · Zbl 1141.65085 · doi:10.1002/num.20254 |
| [17] | Graham, I.G., Scheichl, R.: Coefficient-explicit condition number bounds for overlapping additive Schwarz. In: Langer, U., Discacciati, M., Keyes, D.E., Widlund, O.B., Zulehner, W. (eds.) Domain decomposition methods in science and engineering XVII. Lecture Notes in Computational Science and Engineering, vol. 60, pp. 365–372. Springer, Berlin (2008) |
| [18] | Klawonn A., Rheinbach O.: Inexact FETI-DP methods. Inter. J. Numer. Methods Eng. 69, 284–307 (2007) · Zbl 1194.74420 · doi:10.1002/nme.1758 |
| [19] | Klawonn A., Rheinbach O.: Robust FETI-DP methods for heterogeneous three-dimensional elasticity problems. Comput. Methods Appl. Mech. Eng. 196, 1400–1414 (2007) · Zbl 1173.74428 · doi:10.1016/j.cma.2006.03.023 |
| [20] | Klawonn A., Rheinbach O., Widlund O.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 · doi:10.1137/070688675 |
| [21] | Klawonn A., Widlund O.B.: FETI and Neumann-Neumann iterative substructuring methods: connections and new results. Comm. Pure Appl. Math. 54(1), 57–90 (2001) · Zbl 1023.65120 · doi:10.1002/1097-0312(200101)54:1<57::AID-CPA3>3.0.CO;2-D |
| [22] | Klawonn A., Widlund O.B., Dryja M.: Dual-primal FETI methods for three-dimensional elliptic problems with heterogeneous coefficients. SIAM J. Numer. Anal. 40(1), 159–179 (2002) · Zbl 1032.65031 · doi:10.1137/S0036142901388081 |
| [23] | Langer U., Pechstein C.: Coupled finite and boundary element tearing and interconnecting solvers for non-linear potential problems. ZAMM Z. Angew. Math. Mech. 86(12), 915–931 (2006) · Zbl 1110.78009 · doi:10.1002/zamm.200610294 |
| [24] | Mandel J., Dohrmann C.R.: Convergence of a balancing domain decomposition by constraints and energy minimization. Numer. Lin. Alg. Appl. 10, 639–659 (2003) · Zbl 1071.65558 · doi:10.1002/nla.341 |
| [25] | Mandel J., Dohrmann C.R., Tezaur R.: An algebraic theory for primal and dual substructuring methods by constraints. Appl. Numer. Math. 54, 167–193 (2005) · Zbl 1127.76049 · doi:10.1016/j.apnum.2004.09.022 |
| [26] | Mandel J., Tezaur R.: Convergence of a substrucuring method with Lagrange multipliers. Numer. Math. 73, 473–487 (1996) · Zbl 0880.65087 · doi:10.1007/s002110050201 |
| [27] | Mandel J., Tezaur R.: On the convergence of a dual-primal substructuring method. Numer. Math. 88, 543–558 (2001) · Zbl 1003.65126 · doi:10.1007/s211-001-8014-1 |
| [28] | Of, G.: The all-floating BETI method: Numerical results. In: Langer, U., Discacciati, M., Keyes, D.E., Widlund, O.B., Zulehner, W. (eds.) Domain decomposition methods in science and engineering XVII. Lecture Notes in Computational Science and Engineering, vol. 60, pp. 295–302. Springer, Berlin (2008) |
| [29] | Pechstein, C.: Analysis of dual and dual-primal tearing and interconnecting methods in unbounded domains. SFB-Report 2007-15, SFB. Numerical and Symbolic Scientific Computing. F013, Johannes Kepler University of Linz, August 2007. http://www.sfb013.uni-linz.ac.at/\(\sim\)sfb/reports/2007/pdf-files/rep_07-15_pechstein.pdf |
| [30] | Pechstein, C.: Boundary element tearing and interconnecting methods in unbounded domains. Appl. Num. Math. (2008, to appear) · Zbl 1176.65145 |
| [31] | Rheinbach, O.: FETI: a dual iterative substructuring method for elliptic partial differential equations. Master’s Thesis, Mathematisches Institut, Universität zu Köln, Germany (2002) |
| [32] | Rixen, D., Farhat, C.: Preconditioning the FETI method for problems with intra- and inter-subdomain coefficient jumps. In: Bjørstad, P.E., Espedal, M., Keyes, D. (eds.) Ninth International Conference on Domain Decomposition Methods, pp. 472–479 (1997). http://www.ddm.org/DD9/Rixen.pdf |
| [33] | Rixen D., Farhat C.: A simple and efficient extension of a class of substructure based preconditioners to heterogeneous structural mechanics problems. Int. J. Numer. Methods Eng. 44, 489–516 (1999) · Zbl 0940.74067 · doi:10.1002/(SICI)1097-0207(19990210)44:4<489::AID-NME514>3.0.CO;2-Z |
| [34] | Ruge, J., Stüben, K.: Efficient solution of finite difference and finite element equations by algebraic multigrid (AMG). In: Paddon, D.J., Holstein, H. (eds.) Multigrid Methods for integral and differential equations. IMA Conference Series, pp. 169–212. Clarendon Press, Oxford (1985) · Zbl 0581.65072 |
| [35] | Sarkis M.: Nonstandard coarse spaces and Schwarz methods for elliptic problems with discontinuous coefficients using non-conforming elements. Numer. Math. 77(3), 383–406 (1997) · Zbl 0884.65119 · doi:10.1007/s002110050292 |
| [36] | Scheichl R., Vainikko E.: Additive Schwarz and aggregation-based coarsening for elliptic problems with highly variable coefficients. Computing 80(4), 319–343 (2007) · Zbl 1171.65372 · doi:10.1007/s00607-007-0237-z |
| [37] | Scott L.R., Zhang S.: Finite element interpolation of non-smooth functions satisfying boundary conditions. Math. Comp. 54, 483–493 (1990) · Zbl 0696.65007 · doi:10.1090/S0025-5718-1990-1011446-7 |
| [38] | Toselli A., Widlund O.: Domain decoposition methods: algorithms and theory. Springer Series in Computational Mathematics, vol. 34. Springer, Berlin (2005) · Zbl 1069.65138 |
| [39] | Vanek P., Mandel J., Brezina M.: Algebraic multigrid by smoothed aggregation for 2nd and 4th order elliptic problems. Computing 56(3), 179–196 (1996) · Zbl 0851.65087 · doi:10.1007/BF02238511 |
| [40] | Xu, J., Zhu, Y.: Uniform convergent multigrid methods for elliptic problems with strongly discontinuous coefficients. Math. Mod. Meth. Appl. Sci. Technical Report AM311. Department of Mathematics, Pennsylvania (2007, to appear) |
| [41] | Zheng W., Qi H.: On Friedrichs–Poincaré-type inequalities. J. Math. Anal. Appl 304, 542–551 (2005) · Zbl 1076.26015 · doi:10.1016/j.jmaa.2004.09.066 |
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.
