An overlapping domain decomposition preconditioner for a class of discontinuous Galerkin approximations of advection-diffusion problems
Authors: Caroline Lasser and Andrea Toselli
Journal: Math. Comp. 72 (2003), 1215-1238
MSC (2000): Primary 65F10, 65N22, 65N30, 65N55
Published electronically: January 8, 2003
MathSciNet review: 1972733
Full-text PDF Free Access
Abstract: We consider a scalar advection-diffusion problem and a recently proposed discontinuous Galerkin approximation, which employs discontinuous finite element spaces and suitable bilinear forms containing interface terms that ensure consistency. For the corresponding sparse, nonsymmetric linear system, we propose and study an additive, two-level overlapping Schwarz preconditioner, consisting of a coarse problem on a coarse triangulation and local solvers associated to a family of subdomains. This is a generalization of the corresponding overlapping method for approximations on continuous finite element spaces. Related to the lack of continuity of our approximation spaces, some interesting new features arise in our generalization, which have no analog in the conforming case. We prove an upper bound for the number of iterations obtained by using this preconditioner with GMRES, which is independent of the number of degrees of freedom of the original problem and the number of subdomains. The performance of the method is illustrated by several numerical experiments for different test problems using linear finite elements in two dimensions.
- 1. Douglas N. Arnold, An interior penalty finite element method with discontinuous elements, SIAM J. Numer. Anal. 19 (1982), no. 4, 742–760. MR 664882, https://doi.org/10.1137/0719052
- 2. Xiao-Chuan Cai and Olof B. Widlund, Domain decomposition algorithms for indefinite elliptic problems, SIAM J. Sci. Statist. Comput. 13 (1992), no. 1, 243–258. MR 1145185, https://doi.org/10.1137/0913013
- 3. Xiao-Chuan Cai and Olof B. Widlund, Multiplicative Schwarz algorithms for some nonsymmetric and indefinite problems, SIAM J. Numer. Anal. 30 (1993), no. 4, 936–952. MR 1231321, https://doi.org/10.1137/0730049
- 4. Tony F. Chan, Barry F. Smith, and Jun Zou, Overlapping Schwarz methods on unstructured meshes using non-matching coarse grids, Numer. Math. 73 (1996), no. 2, 149–167. MR 1384228, https://doi.org/10.1007/s002110050189
- 5. Bernardo Cockburn, George E. Karniadakis, and Chi-Wang Shu (eds.), Discontinuous Galerkin methods, Lecture Notes in Computational Science and Engineering, vol. 11, Springer-Verlag, Berlin, 2000. Theory, computation and applications; Papers from the 1st International Symposium held in Newport, RI, May 24–26, 1999. MR 1842160
- 6. Monique Dauge, Elliptic boundary value problems on corner domains, Lecture Notes in Mathematics, vol. 1341, Springer-Verlag, Berlin, 1988. Smoothness and asymptotics of solutions. MR 961439
- 7. Stanley C. Eisenstat, Howard C. Elman, and Martin H. Schultz, Variational iterative methods for nonsymmetric systems of linear equations, SIAM J. Numer. Anal. 20 (1983), no. 2, 345–357. MR 694523, https://doi.org/10.1137/0720023
- 8. X. Feng, O. Karakashan, Two-level non-overlapping Schwarz methods for a discontinuous Galerkin method, 2000, submitted to Siam J. on Numer. Anal.
- 9. P. Houston, C. Schwab, E. Süli, Discontinuous hp-Finite Element Methods for Advection-Diffusion Problems, Technical Report 00-07 (2000), Seminar für Angewandte Mathematik, ETH Zürich. To appear in Math. Comp.
Johnson, Numerical solution of partial differential equations by
the finite element method, Cambridge University Press, Cambridge,
Claes Johnson, Numerical solution of partial differential equations by the finite element method, Studentlitteratur, Lund, 1987. MR 911477
- 11. Axel Klawonn and Luca F. Pavarino, A comparison of overlapping Schwarz methods and block preconditioners for saddle point problems, Numer. Linear Algebra Appl. 7 (2000), no. 1, 1–25. MR 1751992, https://doi.org/10.1002/(SICI)1099-1506(200001/02)7:1<1::AID-NLA183>3.3.CO;2-A
- 12. Alfred H. Schatz, An observation concerning Ritz-Galerkin methods with indefinite bilinear forms, Math. Comp. 28 (1974), 959–962. MR 0373326, https://doi.org/10.1090/S0025-5718-1974-0373326-0
- 13. Ch. Schwab, 𝑝- and ℎ𝑝-finite element methods, Numerical Mathematics and Scientific Computation, The Clarendon Press, Oxford University Press, New York, 1998. Theory and applications in solid and fluid mechanics. MR 1695813
- 14. Barry F. Smith, Petter E. Bjørstad, and William D. Gropp, Domain decomposition, Cambridge University Press, Cambridge, 1996. Parallel multilevel methods for elliptic partial differential equations. MR 1410757
- 15. R. Verfürth, A Review of A Posteriori Error Estimation and Adaptive Mesh-Refinement Techniques (1996), Wiley and Teubner.
- 16. Olof B. Widlund, Domain decomposition methods for elliptic partial differential equations, Error control and adaptivity in scientific computing (Antalya, 1998) NATO Sci. Ser. C Math. Phys. Sci., vol. 536, Kluwer Acad. Publ., Dordrecht, 1999, pp. 325–354. MR 1735135
- D. Arnold, An Interior Penalty Finite Element Method with Discontinuous Elements, SIAM J. Numer. Anal. 19 (1982), 742-760. MR 83f:65173
- X. Cai, O. Widlund, Domain Decomposition Algorithms for Indefinite Elliptic Problems, SIAM J. Sci. Statist. Comput. 13(1) (1992), 243-258. MR 92i:65181
- X. Cai, O. Widlund, Multiplicative Schwarz Algorithms for Some Nonsymmetric and Indefinite Problems, SIAM J. Num. Anal. 30(4) (1993), 936-952. MR 94j:65141
- T. Chan, B. Smith, J. Zou, Overlapping Schwarz Methods on Unstructured Meshes using Non-matching Coarse Grids, Numer. Math. 73(2) (1996), 149-167. MR 97h:65135
- B. Cockburn, G. Karniadakis, C. Shu (Eds.), Discontinuous Galerkin Methods, Lecture Notes in Computational Science and Engineering 11 (2000), Springer-Verlag MR 2002b:65004
- M. Dauge, Elliptic Boundary Value Problems on Corner Domains, Lecture Notes in Mathematics 1341 (1988), Springer-Verlag MR 91a:35078
- S. Eisenstat, H. Elman, M. Schultz, Variational iterative methods for non-symmetric systems of linear equations, SIAM J. Numer. Anal. 20 (1983), 345-357 MR 84h:65030
- X. Feng, O. Karakashan, Two-level non-overlapping Schwarz methods for a discontinuous Galerkin method, 2000, submitted to Siam J. on Numer. Anal.
- P. Houston, C. Schwab, E. Süli, Discontinuous hp-Finite Element Methods for Advection-Diffusion Problems, Technical Report 00-07 (2000), Seminar für Angewandte Mathematik, ETH Zürich. To appear in Math. Comp.
- C. Johnson, Numerical Solution of Partial Differential Equations by the Finite Element Method (1987), Cambridge University Press MR 89b:65003a
- A. Klawonn, L. Pavarino, A comparison of overlapping Schwarz methods and block preconditioners for saddle point problems, Num. Lin. Alg. Appl. 7 (2000), pp. 1-25 MR 2000m:65149
- A. Schatz, An Observation Concerning Ritz-Galerkin Methods with Indefinite Bilinear Forms, Math. Comp. 28(128) (1974), 959-962. MR 51:9526
- C. Schwab, p- and hp-Finite Element Methods. Theory and Applications to Solid and Fluid Mechanics (1998), Oxford University Press. MR 2000d:65003
- B. Smith, P. Bjørstad, W. Gropp, Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations (1996), Cambridge University Press. MR 98g:65003
- R. Verfürth, A Review of A Posteriori Error Estimation and Adaptive Mesh-Refinement Techniques (1996), Wiley and Teubner.
- O. Widlund, Domain Decomposition Methods for Elliptic Partial Differential Equations, NATO Sci. Ser. C Math. Phys. Sci. 536 (1998), Kluwer Acad. Publ., 325-354 MR 2000k:65228
Affiliation: Center for Mathematical Sciences, Technische Universität München, D-85748 Garching bei München, Germany
Affiliation: Seminar for Applied Mathematics, ETH Zürich, Rämisstr. 101, CH-8092 Zürich, Switzerland
Keywords: Advection-diffusion problem, domain decomposition, discontinuous Galerkin approximation, preconditioning
Received by editor(s): November 14, 2000
Received by editor(s) in revised form: April 3, 2001
Published electronically: January 8, 2003
Additional Notes: The work of the first author was supported by the Studienstiftung des Deutschen Volkes while she was visiting the Courant Institute of Mathematical Sciences
Most of this work was carried out while the second author was affiliated to the Courant Institute of Mathematical Sciences, New York, and supported in part by the Applied Mathematical Sciences Program of the U.S. Department of Energy under Contract DEFGO288ER25053.
Article copyright: © Copyright 2003 American Mathematical Society