×

zbMATH — the first resource for mathematics

Domain decomposition for multiscale PDEs. (English) Zbl 1141.65084
The authors consider additive Schwarz domain decomposition preconditioners for piecewise linear finite element approximations of elliptic partial differential equations with highly variable coefficients. These preconditioners combine local solvers on general overlapping subdomains together with a global solver on a general coarse space of functions on a coarse grid. An analysis of the preconditioned matrix is performed, which shows that its condition number depends on the variable coefficient in the partial differential equation as well as on the coarse mesh and overlap parameters.
These results show that with a good choice of subdomains and coarse space basis functions, the preconditioner can still be robust even for large coefficient variation inside domains. Further, these estimates prove precisely that the previously made empirical observation that the use of low-energy coarse spaces can lead to robust preconditioners. Some numerical experiments are carried out in supporting the theoretical results.

MSC:
65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
65F10 Iterative numerical methods for linear systems
65F35 Numerical computation of matrix norms, conditioning, scaling
35J25 Boundary value problems for second-order elliptic equations
Software:
GAUSSIAN
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aarnes J., Hou T.Y. (2002). Multiscale domain decomposition methods for elliptic problems with high aspect ratios. Acta Math. Appl.Sinica Engl. Ser. 18: 63–76 · Zbl 1003.65142 · doi:10.1007/s102550200004
[2] Cai X., Nielsen B.F., Tveito A. (1999). An analysis of a preconditioner for the discretized pressure equation arising in reservoir simulation. IMA J Numer. Anal. 19: 291–316 · Zbl 0932.65114 · doi:10.1093/imanum/19.2.291
[3] Carvalho L.M., Giraud L., Le Tallec P. (2001). Algebraic two-level preconditioners for the Schur complement method. SIAM J. Sci. Comp. 22: 1987–2005 · Zbl 0990.65134 · doi:10.1137/S1064827598340809
[4] Chan T.F., Smith B.F., Zou J. (1996). Overlapping Schwarz methods on unstructured meshes using non-matching coarse grids. Numer. Math. 73: 149–167 · Zbl 0879.65082 · doi:10.1007/s002110050189
[5] Chan T.F., Mathew T. (1994). Domain Decomposition Methods, Acta Numerica 1994. Cambridge University Press, Cambridge
[6] Chen J., Cui J. (2004). A multiscale finite element method for elliptic problems with highly oscillating coefficients. Appl. Numer. Math. 50: 1–13 · Zbl 1066.65122 · doi:10.1016/j.apnum.2003.12.002
[7] Cliffe K.A., Graham I.G., Scheichl R., Stals L. (2000). Parallel computation of flow in heterogeneous media modelled by mixed finite elements. J. Comp. Phys. 164: 258–282 · Zbl 0995.76044 · doi:10.1006/jcph.2000.6593
[8] De Zeeuw P.M. (1990). Matrix-dependent prolongations and restrictions in a blackbox multigrid solver. J. Comp. Appl. Math. 33: 1–27 · Zbl 0717.65099 · doi:10.1016/0377-0427(90)90252-U
[9] Dohrmann, C.R., Klawonn, A., Widlund, O.B.: Extending the theory for domain decomposition to irregular subdomains. Submitted to Lect. Notes Comput. Sci. Eng. (17th International Conference on Domain Decomposition Methods in Science and Engineering, Strobl, Austria, July 2006) · Zbl 1140.65365
[10] Dryja M., Widlund O.B. (1994). Domain decomposition algorithms with small overlap. SIAM J. Sci. Comp. 15: 604–620 · Zbl 0802.65119 · doi:10.1137/0915040
[11] Dryja, M., Widlund, O.B.: Some recent results on Schwarz type domain decomposition algorithms. In: Mandel, J., Farhat, C., Cai, X.-C. (eds.) Proceedings of 6th International Confererence on Domain Decomposition Methods, Como, Italy, 1992. AMS Contemporary Math. 157, 53–62 (1994) · Zbl 0812.65108
[12] Dryja M., Sarkis M.V., Widlund O.B. (1996). Multilevel Schwarz methods for elliptic problems with discontinuous coefficients in three dimensions. Numer. Math. 72: 313–348 · Zbl 0857.65131 · doi:10.1007/s002110050172
[13] E W., Engquist B. (2004). Analysis of the heterogeneous multiscale method for elliptic homogenisation problems. J. Am. Math. Soc. 18: 121–156 · Zbl 1060.65118 · doi:10.1090/S0894-0347-04-00469-2
[14] Engquist B., Luo E. (1997). Convergence of a multigrid method for elliptic equations with highly oscillatory coefficients. SIAM J. Numer. Anal. 34: 2254–2273 · Zbl 0890.65107 · doi:10.1137/S0036142995289408
[15] Giraud L., Guevara F., Tuminaro R.S., Vasquez (2003). Grid transfer operators for highly-variable coefficient problems in two-level non-overlapping domain decomposition methods. Numer. Linear Algebra Appl. 10: 467–484 · Zbl 1071.65556 · doi:10.1002/nla.324
[16] Graham I.G., Hagger M.J. (1999). Unstructured additive Schwarz-CG method for elliptic problems with highly discontinuous coefficients. SIAM J. Sci. Comp. 20: 2041–2066 · Zbl 0943.65147 · doi:10.1137/S1064827596305593
[17] Graham, I.G., Hagger, M.J.: Additive Schwarz, CG and discontinuous coefficients. In: Bjørstad, P., Espedal, M., Keyes, D.E. (eds.) Proceedings of 9th International Conference on Domain Decomposition Methods, Bergen, Norway, 1996. Domain Decomposition Press, Bergen (1998) · Zbl 0943.65147
[18] Graham, I.G., Lechner, P.O.: Domain Decomposition for heterogeneous media, In: Widlund, O.B., Keyes, D.E. (eds.) Proceedings of 16th International Conference on Domain Decomposition Methods, New York (2005). Springer Lecture Notes in Computational Science and Engineering 55 (2007). Available electronically at http://cims.nyu.edu/dd16/
[19] Graham, I.G., Scheichl, R.: Robust Domain Decomposition Algorithms for Multiscale PDEs. Numer. Methods Partial Differ. Equ. (2007, to appear) · Zbl 1141.65085
[20] Graham, I.G., Scheichl, R.: Coefficient-explicit condition number bounds for overlapping additive Schwarz. Submitted to Lect. Notes Comput. Sci. Eng. (17th International Conference on Domain Decomposition Methods in Science and Engineering, Strobl, Austria, July 2006) · Zbl 1139.65330
[21] Hou T.Y., Wu X.-H. (1997). A multiscale finite element method for elliptic problems in composite materials and porous media. J. Comput. Phys. 134: 169–189 · Zbl 0880.73065 · doi:10.1006/jcph.1997.5682
[22] Hou T.Y., Wu X.-H., Cai Z. (1999). Convergence of a multiscale finite element method for elliptic problems with rapidly oscillating coefficients. Math. Comput. 68: 913–943 · Zbl 0922.65071 · doi:10.1090/S0025-5718-99-01077-7
[23] Jones J.E., Vassilevski P.S. (2001). AMGe based on element agglomeration. SIAM J. Sci. Comput. 23: 109–133 · Zbl 0992.65140 · doi:10.1137/S1064827599361047
[24] Jüngel A., Unterreiter A. (2005). Discrete minimum and maximum principles for finite element approximations of non-monotone elliptic equations. Numer. Math. 99: 485–508 · Zbl 1069.65128 · doi:10.1007/s00211-004-0554-5
[25] Kozintsev, B., Kedem, B.: Gaussian package, University of Maryland. Available at http://www.math.umd.edu/bnk/bak/generate.cgi (1999)
[26] Lechner, P.O.: Iterative methods for heterogeneous media. PhD Thesis, University of Bath (2006) · Zbl 1100.81510
[27] McLean W. (2000). Strongly Elliptic Systems and Boundary Integral Equations. Cambridge University Press, Cambridge · Zbl 0948.35001
[28] Neuss N., Jäger W., Wittum G. (2001). Homogenization and multigrid. Computing 66: 1–26 · Zbl 0992.35013 · doi:10.1007/s006070170036
[29] Sarkis, M.: Partition of unity coarse spaces: Enhanced versions, discontinuous coefficients, and applications to elasticity. In: Herrera, I., Keyes, D.E., Widlund, O.B., Yates, R., (eds.) Proceedings of 14th International Conference Domain Decomposition Methods, DDM. org (2003)
[30] Scheichl, R., Vainikko, E.: Robust aggregation-based coarsening for additive Schwarz in the case of highly variable coefficients. In: Wesseling, P., Onate, E., Periaux, J. (eds.) Proceedings of European Conference on Computational Fluid Dynamics, ECCOMAS CFD 2006, Egmond aan Zee, The Netherlands (2006) · Zbl 1171.65372
[31] Scheichl, R., Vainikko, E.: Additive Schwarz and aggregation-based coarsening for elliptic problems with highly variable coefficients, submitted, BICS preprint 9/06 (2006). Available electronically at http://www.bath.ac.uk/math-sci/BICS/
[32] Scott L.R., Zhang S. (1990). Finite element interpolation of non-smooth functions satisfying boundary conditions. Math. Comp. 54: 483–493 · Zbl 0696.65007 · doi:10.1090/S0025-5718-1990-1011446-7
[33] Toselli A., Widlund O. (2005). Domain Decomposition Methods Algorithms and Theory. Springer, Heidelberg · Zbl 1069.65138
[34] Vuik K., Segal A., Meijerink J.A. (2000). An efficient preconditioned CG method for the solution of a class of layered problems with extreme contrasts in the coefficients. J. Comput. Phys. 21: 1632–1649 · Zbl 0945.76048
[35] Wan W.L., Chan T.F., Smith B. (2000). An energy-minimizing interpolation for robust multigrid methods. SIAM J. Sci. Comput. 21: 1632–1649 · Zbl 0966.65098 · doi:10.1137/S1064827598334277
[36] Xu J., Zikatanov L. (1999). A monotone finite element scheme for convection–diffusion equations. Math. Comp. 68: 1426–1446 · Zbl 0931.65111 · doi:10.1090/S0025-5718-99-01148-5
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.