Schwarz domain decomposition preconditioners for discontinuous Galerkin approximations of elliptic problems: non-overlapping case

Paola F. Antonietti; Blanca Ayuso

ESAIM: Mathematical Modelling and Numerical Analysis (2007)

  • Volume: 41, Issue: 1, page 21-54
  • ISSN: 0764-583X

Abstract

top

We propose and study some new additive, two-level non-overlapping Schwarz preconditioners for the solution of the algebraic linear systems arising from a wide class of discontinuous Galerkin approximations of elliptic problems that have been proposed up to now. In particular, two-level methods for both symmetric and non-symmetric schemes are introduced and some interesting features, which have no analog in the conforming case, are discussed. Both the construction and analysis of the proposed domain decomposition methods are presented in a unified framework. For symmetric schemes, it is shown that the condition number of the preconditioned system is of order O(H/h), where H and h are the mesh sizes of the coarse and fine grids respectively, which are assumed to be nested. For non-symmetric schemes, we show by numerical computations that the Eisenstat et al. [SIAM J. Numer. Anal.20 (1983) 345–357] GMRES convergence theory, generally used in the analysis of Schwarz methods for non-symmetric problems, cannot be applied even if the numerical results show that the GMRES applied to the preconditioned systems converges in a finite number of steps and the proposed preconditioners seem to be scalable. Extensive numerical experiments to validate our theory and to illustrate the performance and robustness of the proposed two-level methods are presented.


How to cite

top

Antonietti, Paola F., and Ayuso, Blanca. "Schwarz domain decomposition preconditioners for discontinuous Galerkin approximations of elliptic problems: non-overlapping case." ESAIM: Mathematical Modelling and Numerical Analysis 41.1 (2007): 21-54. <http://eudml.org/doc/250049>.

@article{Antonietti2007,
abstract = {
We propose and study some new additive, two-level non-overlapping Schwarz preconditioners for the solution of the algebraic linear systems arising from a wide class of discontinuous Galerkin approximations of elliptic problems that have been proposed up to now. In particular, two-level methods for both symmetric and non-symmetric schemes are introduced and some interesting features, which have no analog in the conforming case, are discussed. Both the construction and analysis of the proposed domain decomposition methods are presented in a unified framework. For symmetric schemes, it is shown that the condition number of the preconditioned system is of order O(H/h), where H and h are the mesh sizes of the coarse and fine grids respectively, which are assumed to be nested. For non-symmetric schemes, we show by numerical computations that the Eisenstat et al. [SIAM J. Numer. Anal.20 (1983) 345–357] GMRES convergence theory, generally used in the analysis of Schwarz methods for non-symmetric problems, cannot be applied even if the numerical results show that the GMRES applied to the preconditioned systems converges in a finite number of steps and the proposed preconditioners seem to be scalable. Extensive numerical experiments to validate our theory and to illustrate the performance and robustness of the proposed two-level methods are presented.
},
author = {Antonietti, Paola F., Ayuso, Blanca},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis},
keywords = {Domain decomposition methods; discontinuous Galerkin; elliptic problems.; domain decomposition methods; discontinuous Galerkin methods; elliptic problems; Poisson equation; additive Schwarz preconditioners; stability; numerical experiments},
language = {eng},
month = {4},
number = {1},
pages = {21-54},
publisher = {EDP Sciences},
title = {Schwarz domain decomposition preconditioners for discontinuous Galerkin approximations of elliptic problems: non-overlapping case},
url = {http://eudml.org/doc/250049},
volume = {41},
year = {2007},
}

TY - JOUR
AU - Antonietti, Paola F.
AU - Ayuso, Blanca
TI - Schwarz domain decomposition preconditioners for discontinuous Galerkin approximations of elliptic problems: non-overlapping case
JO - ESAIM: Mathematical Modelling and Numerical Analysis
DA - 2007/4//
PB - EDP Sciences
VL - 41
IS - 1
SP - 21
EP - 54
AB - 
We propose and study some new additive, two-level non-overlapping Schwarz preconditioners for the solution of the algebraic linear systems arising from a wide class of discontinuous Galerkin approximations of elliptic problems that have been proposed up to now. In particular, two-level methods for both symmetric and non-symmetric schemes are introduced and some interesting features, which have no analog in the conforming case, are discussed. Both the construction and analysis of the proposed domain decomposition methods are presented in a unified framework. For symmetric schemes, it is shown that the condition number of the preconditioned system is of order O(H/h), where H and h are the mesh sizes of the coarse and fine grids respectively, which are assumed to be nested. For non-symmetric schemes, we show by numerical computations that the Eisenstat et al. [SIAM J. Numer. Anal.20 (1983) 345–357] GMRES convergence theory, generally used in the analysis of Schwarz methods for non-symmetric problems, cannot be applied even if the numerical results show that the GMRES applied to the preconditioned systems converges in a finite number of steps and the proposed preconditioners seem to be scalable. Extensive numerical experiments to validate our theory and to illustrate the performance and robustness of the proposed two-level methods are presented.

LA - eng
KW - Domain decomposition methods; discontinuous Galerkin; elliptic problems.; domain decomposition methods; discontinuous Galerkin methods; elliptic problems; Poisson equation; additive Schwarz preconditioners; stability; numerical experiments
UR - http://eudml.org/doc/250049
ER -

References

top
  1. R.A. Adams, Sobolev spaces. Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, Pure and Applied Mathematics, Vol. 65 (1975).  Zbl0314.46030
  2. P.F. Antonietti, A. Buffa and I. Perugia, Discontinuous Galerkin approximation of the Laplace eigenproblem. Comput. Methods Appl. Mech. Engrg.195 (2006) 3483–3503.  Zbl1168.65410
  3. D.N. Arnold, An interior penalty finite element method with discontinuous elements. SIAM J. Numer. Anal.19 (1982) 742–760.  Zbl0482.65060
  4. D.N. Arnold, F. Brezzi, B. Cockburn and L.D. Marini, Unified analysis of discontinuous Galerkin methods for elliptic problems. SIAM J. Numer. Anal.39 (2001/02) 1749–1779 (electronic).  Zbl1008.65080
  5. I. Babuška and M. Zlámal, Nonconforming elements in the finite element method with penalty. SIAM J. Numer. Anal.10 (1973) 863–875.  Zbl0237.65066
  6. F. Bassi and S. Rebay, A high-order accurate discontinuous finite element method for the numerical solution of the compressible Navier-Stokes equations. J. Comput. Phys.131 (1997) 267–279.  Zbl0871.76040
  7. F. Bassi, S. Rebay, G. Mariotti, S. Pedinotti and M. Savini, A high-order accurate discontinuous finite element method for inviscid and viscous turbomachinery flows, in Proceedings of the 2nd European Conference on Turbomachinery Fluid Dynamics and Thermodynamics, R. Decuypere and G. Dibelius Eds., Antwerpen, Belgium (1997) 99–108, Technologisch Instituut.  
  8. C.E. Baumann and J.T. Oden, A discontinuous hp finite element method for convection-diffusion problems. Comput. Methods Appl. Mech. Engrg.175 (1999) 311–341.  Zbl0924.76051
  9. S.C. Brenner, Poincaré-Friedrichs inequalities for piecewise H1 functions. SIAM J. Numer. Anal.41 (2003) 306–324 (electronic).  Zbl1045.65100
  10. S.C. Brenner and K. Wang, Two-level additive Schwarz preconditioners for C0 interior penalty methods. Numer. Math.102 (2005) 231–255.  Zbl1088.65108
  11. F. Brezzi, G. Manzini, D. Marini, P. Pietra and A. Russo, Discontinuous Galerkin approximations for elliptic problems. Numer. Methods Partial Differ. Equ.16 (2000) 365–378.  Zbl0957.65099
  12. F. Brezzi, L.D. Marini and E. Süli, Discontinuous Galerkin methods for first-order hyperbolic problems. Math. Models Methods Appl. Sci.14 (2004) 1893–1903.  Zbl1070.65117
  13. X.-C. Cai and O.B. Widlund, Domain decomposition algorithms for indefinite elliptic problems. SIAM J. Sci. Statist. Comput.13 (1992) 243–258.  Zbl0746.65085
  14. P.E. Castillo, Local Discontinuous Galerkin methods for convection-diffusion and elliptic problems. Ph.D. thesis, University of Minnesota, Minneapolis (2001).  
  15. P. Castillo, B. Cockburn, I. Perugia and D. Schötzau, An a priori error analysis of the local discontinuous Galerkin method for elliptic problems. SIAM J. Numer. Anal.38 (2000) 1676–1706 (electronic).  Zbl0987.65111
  16. P.G. Ciarlet, The finite element method for elliptic problems. North-Holland Publishing Co., Amsterdam, Studies in Mathematics and its Applications, Vol. 4 (1978).  Zbl0383.65058
  17. B. Cockburn, Discontinuous Galerkin methods for convection-dominated problems, in High-order methods for computational physics, Springer, Berlin, Lect. Notes Comput. Sci. Eng.9 (1999) 69–224.  Zbl0937.76049
  18. B. Cockburn and C.-W. Shu, The local discontinuous Galerkin method for time-dependent convection-diffusion systems. SIAM J. Numer. Anal.35 (1998) 2440–2463 (electronic).  Zbl0927.65118
  19. B. Cockburn, G.E. Karniadakis, and C.-W. Shu. The development of discontinuous Galerkin methods, in Discontinuous Galerkin methods (Newport, RI, 1999), Springer, Berlin, Lect. Notes Comput. Sci. Eng.11 (2000) 3–50.  Zbl0989.76045
  20. C. Dawson, S. Sun and M.F. Wheeler, Compatible algorithms for coupled flow and transport. Comput. Methods Appl. Mech. Engrg.193 (2004) 2565–2580.  Zbl1067.76565
  21. J. Douglas, Jr., and T. Dupont. Interior penalty procedures for elliptic and parabolic Galerkin methods, in Computing methods in applied sciences (Second Internat. Sympos., Versailles, 1975), Springer, Berlin, Lect. Notes Phys.58 (1976) 207–216.  
  22. S.C. Eisenstat, H.C. Elman and M.H. Schultz, Variational iterative methods for nonsymmetric systems of linear equations. SIAM J. Numer. Anal.20 (1983) 345–357.  Zbl0524.65019
  23. X. Feng and O.A. Karakashian, Two-level additive Schwarz methods for a discontinuous Galerkin approximation of second order elliptic problems. SIAM J. Numer. Anal.39 (2001) 1343–1365 (electronic).  Zbl1007.65104
  24. X. Feng and O.A. Karakashian, Analysis of two-level overlapping additive Schwarz preconditioners for a discontinuous Galerkin method. In Domain decomposition methods in science and engineering (Lyon, 2000), Theory Eng. Appl. Comput. Methods, Internat. Center Numer. Methods Eng. (CIMNE), Barcelona (2002) 237–245.  Zbl1026.65121
  25. G.H. Golub and C.F. Van Loan, Matrix computations. Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, third edition (1996).  Zbl0865.65009
  26. J. Gopalakrishnan and G. Kanschat. Application of unified DG analysis to preconditioning DG methods, in Computational Fluid and Solid Mechanics 2003, K.J. Bathe Ed., Elsevier (2003) 1943–1945.  
  27. J. Gopalakrishnan and G. Kanschat, A multilevel discontinuous Galerkin method. Numer. Math.95 (2003) 527–550.  Zbl1044.65084
  28. B. Heinrich and K. Pietsch, Nitsche type mortaring for some elliptic problem with corner singularities. Computing68 (2002) 217–238.  Zbl1002.65124
  29. P. Houston and E. Süli, hp-adaptive discontinuous Galerkin finite element methods for first-order hyperbolic problems. SIAM J. Sci. Comput.23 (2001) 1226–1252 (electronic).  Zbl1029.65130
  30. C. Lasser and A. Toselli, An overlapping domain decomposition preconditioner for a class of discontinuous Galerkin approximations of advection-diffusion problems. Math. Comp.72 (2003) 1215–1238 (electronic).  Zbl1038.65135
  31. P. Le Tallec, Domain decomposition methods in computational mechanics. Comput. Mech. Adv.1 (1994) 121–220.  Zbl0802.73079
  32. P.-L. Lions, On the Schwarz alternating method. I, in First International Symposium on Domain Decomposition Methods for Partial Differential Equations (Paris, 1987), SIAM, Philadelphia, PA (1988) 1–42.  
  33. P.-L. Lions, On the Schwarz alternating method. II. Stochastic interpretation and order properties, in Domain decomposition methods (Los Angeles, CA, 1988), SIAM, Philadelphia, PA (1989) 47–70.  
  34. P.-L. Lions, On the Schwarz alternating method. III. A variant for nonoverlapping subdomains, in Third International Symposium on Domain Decomposition Methods for Partial Differential Equations (Houston, TX, 1989), SIAM, Philadelphia, PA (1990) 202–223.  
  35. W.H. Reed and T. Hill, Triangular mesh methods for the neutron transport equation. Technical Report LA-UR-73-479, Los Alamos Scientific Laboratory (1973).  
  36. B. Rivière, M.F. Wheeler and V. Girault, Improved energy estimates for interior penalty, constrained and discontinuous Galerkin methods for elliptic problems. I. Comput. Geosci.3 (1999) 337–360.  Zbl0951.65108
  37. B. Rivière, M.F. Wheeler and V. Girault, A priori error estimates for finite element methods based on discontinuous approximation spaces for elliptic problems. SIAM J. Numer. Anal.39 (2001) 902–931 (electronic).  Zbl1010.65045
  38. Y. Saad and M.H. Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Statist. Comput.7 (1986) 856–869.  Zbl0599.65018
  39. M. Sarkis and D.B. Szyld, Optimal left and right additive Schwarz preconditioning for Minimal Residual methods with euclidean and energy norms. Comput. Methods Appl. Mech. Engrg.196 (2007) 1612–1621.  Zbl1173.65366
  40. B.F. Smith, P.E. Bjørstad and W.D. Gropp, Domain decomposition. Cambridge University Press, Cambridge, Parallel multilevel methods for elliptic partial differential equations (1996).  Zbl0857.65126
  41. G. Starke, Field-of-values analysis of preconditioned iterative methods for nonsymmetric elliptic problems. Numer. Math.78 (1997) 103–117.  Zbl0888.65037
  42. R. Stenberg, Mortaring by a method of J. A. Nitsche, in Computational mechanics (Buenos Aires, 1998), pages CD–ROM file. Centro Internac. Métodos Numér. Ing., Barcelona (1998).  
  43. A. Toselli and O. Widlund, Domain decomposition methods–algorithms and theory, Springer Series in Computational Mathematics34, Springer-Verlag, Berlin (2005).  Zbl1069.65138
  44. M.F. Wheeler, An elliptic collocation-finite element method with interior penalties. SIAM J. Numer. Anal.15 (1978) 152–161.  Zbl0384.65058
  45. J.H. Wilkinson, The algebraic eigenvalue problem. Monographs on Numerical Analysis, The Clarendon Press Oxford University Press, New York (1988), Oxford Science Publications.  
  46. J. Xu, Iterative methods by space decomposition and subspace correction. SIAM Rev.34 (1992) 581–613.  Zbl0788.65037
  47. J. Xu and L. Zikatanov, The method of alternating projections and the method of subspace corrections in Hilbert space. J. Amer. Math. Soc.15 (2002) 573–597 (electronic).  Zbl0999.47015
  48. J. Xu and J. Zou. Some nonoverlapping domain decomposition methods. SIAM Rev.40 (1998) 857–914 (electronic).  Zbl0913.65115

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.