Analysis of two-level domain decomposition preconditioners based on aggregation

Marzio Sala

ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique (2004)

  • Volume: 38, Issue: 5, page 765-780
  • ISSN: 0764-583X

Abstract

top
In this paper we present two-level overlapping domain decomposition preconditioners for the finite-element discretisation of elliptic problems in two and three dimensions. The computational domain is partitioned into overlapping subdomains, and a coarse space correction is added. We present an algebraic way to define the coarse space, based on the concept of aggregation. This employs a (smoothed) aggregation technique and does not require the introduction of a coarse grid. We consider a set of assumptions on the coarse basis functions, to ensure bound for the resulting preconditioned system. These assumptions only involve geometrical quantities associated to the aggregates, namely their diameter and the overlap. A condition number which depends on the product of the relative overlap among the subdomains and the relative overlap among the aggregates is proved. Numerical experiments on a model problem are reported to illustrate the performance of the proposed preconditioners.

How to cite

top

Sala, Marzio. "Analysis of two-level domain decomposition preconditioners based on aggregation." ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique 38.5 (2004): 765-780. <http://eudml.org/doc/245380>.

@article{Sala2004,
abstract = {In this paper we present two-level overlapping domain decomposition preconditioners for the finite-element discretisation of elliptic problems in two and three dimensions. The computational domain is partitioned into overlapping subdomains, and a coarse space correction is added. We present an algebraic way to define the coarse space, based on the concept of aggregation. This employs a (smoothed) aggregation technique and does not require the introduction of a coarse grid. We consider a set of assumptions on the coarse basis functions, to ensure bound for the resulting preconditioned system. These assumptions only involve geometrical quantities associated to the aggregates, namely their diameter and the overlap. A condition number which depends on the product of the relative overlap among the subdomains and the relative overlap among the aggregates is proved. Numerical experiments on a model problem are reported to illustrate the performance of the proposed preconditioners.},
author = {Sala, Marzio},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique},
keywords = {elliptic equations; domain decomposition; Schwarz methods; aggregation coarse corrections; domain decomposition method; preconditioning; aggregation; finite-element; elliptic problems},
language = {eng},
number = {5},
pages = {765-780},
publisher = {EDP-Sciences},
title = {Analysis of two-level domain decomposition preconditioners based on aggregation},
url = {http://eudml.org/doc/245380},
volume = {38},
year = {2004},
}

TY - JOUR
AU - Sala, Marzio
TI - Analysis of two-level domain decomposition preconditioners based on aggregation
JO - ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique
PY - 2004
PB - EDP-Sciences
VL - 38
IS - 5
SP - 765
EP - 780
AB - In this paper we present two-level overlapping domain decomposition preconditioners for the finite-element discretisation of elliptic problems in two and three dimensions. The computational domain is partitioned into overlapping subdomains, and a coarse space correction is added. We present an algebraic way to define the coarse space, based on the concept of aggregation. This employs a (smoothed) aggregation technique and does not require the introduction of a coarse grid. We consider a set of assumptions on the coarse basis functions, to ensure bound for the resulting preconditioned system. These assumptions only involve geometrical quantities associated to the aggregates, namely their diameter and the overlap. A condition number which depends on the product of the relative overlap among the subdomains and the relative overlap among the aggregates is proved. Numerical experiments on a model problem are reported to illustrate the performance of the proposed preconditioners.
LA - eng
KW - elliptic equations; domain decomposition; Schwarz methods; aggregation coarse corrections; domain decomposition method; preconditioning; aggregation; finite-element; elliptic problems
UR - http://eudml.org/doc/245380
ER -

References

top
  1. [1] M. Brezina, Robust iterative method on unstructured meshes. Ph.D. Thesis, University of Colorado at Denver (1997). 
  2. [2] M. Brezina and P. Vaněk, A black–box iterative solver based on a two–level Schwarz method. Computing 63 (1999) 233–263. Zbl0951.65133
  3. [3] O. Broeker, M.J. Grote, C. Mayer and A. Reusken, Robust parallel smoothing for multigrid via sparse approximate inverses. SIAM J. Sci. Comput. 23 (2001) 1396–1417. Zbl1004.65043
  4. [4] M. Dryja and O.B. Widlund, Domain decomposition algorithms with small overlap. SIAM J. Sci. Comput. 15 (1994) 604–620. Zbl0802.65119
  5. [5] M. Dryja and O.B. Widlund, Schwarz methods of Neumann-Neumann type for three-dimensional elliptic finite element problems. Comm. Pure Appl. Math. 48 (1995) 121–155. Zbl0824.65106
  6. [6] L. Formaggia, A. Scheinine and A. Quarteroni, A numerical investigation of Schwarz domain decomposition techniques for elliptic problems on unstructured grids. Math. Comput. Simulations 44 (1994) 313–330. Zbl1017.65524
  7. [7] G.H. Golub and C.F. van Loan, Matrix Computations. The Johns Hopkins University Press, Baltimore, Maryland (1983). Zbl0559.65011MR733103
  8. [8] L. Jenkins, T. Kelley, C.T. Miller and C.E. Kees, An aggregation-based domain decomposition preconditioner for groundwater flow. Technical Report TR00–13, Department of Mathematics, North Carolina State University (2000). Zbl1036.65109
  9. [9] C.E. Kees, C.T. Miller, E.W. Jenkins and C.T. Kelley, Versatile multilevel Schwarz preconditioners for multiphase flow. Technical Report CRSC-TR01-32, Center for Research in Scientific Computation, North Carolina State University (2001). Zbl1090.76054
  10. [10] C. Lasser and A. Toselli, An overlapping domain decomposition preconditioner for a class of discontinuous Galerkin approximations of advection-diffusion problems. Technical Report 810, Dept. of Computer Science, Courant Institute (2000). Math. Comput. 72 (2003) 1215–1238. Zbl1038.65135
  11. [11] C. Lasser and A. Toselli, Convergence of some two-level overlapping domain decomposition preconditioners with smoothed aggregation coarse spaces. Technical Report TUM-M0109, Technische Universität München (2001). Zbl1007.65082MR1962683
  12. [12] W. Leontief, The structure of the American Economy. Oxford University Press, New York (1951). 
  13. [13] J. Mandel and B. Sekerka, A local convergence proof for the iterative aggregation method. Linear Algebra Appl. 51 (1983) 163–172. Zbl0494.65014
  14. [14] L. Paglieri, A. Scheinine, L. Formaggia and A. Quarteroni, Parallel conjugate gradient with Schwarz preconditioner applied to fluid dynamics problems, in Parallel Computational Fluid Dynamics, Algorithms and Results using Advanced Computer, Proceedings of Parallel CFD’96, P. Schiano et al., Eds. (1997) 21–30. 
  15. [15] A. Quarteroni and A. Valli, Numerical Approximation of Partial Differential Equations. Springer-Verlag, Berlin (1994). Zbl0803.65088MR1299729
  16. [16] A. Quarteroni and A. Valli, Domain Decomposition Methods for Partial Differential Equations. Oxford University Press, Oxford (1999). Zbl0931.65118MR1857663
  17. [17] M. Sala and L. Formaggia, Parallel Schur and Schwarz based preconditioners and agglomeration coarse corrections for CFD problems. Technical Report 15, DMA-EPFL (2001). 
  18. [18] M. Sala and L. Formaggia, Algebraic coarse grid operators for domain decomposition based preconditioners, in Parallel Computational Fluid Dynamics – Practice and Theory, P. Wilders, A. Ecer, J. Periaux, N. Satofuka and P. Fox, Eds., Elsevier Science, The Netherlands (2002) 119–126. 
  19. [19] B.F. Smith, P. Bjorstad and W.D. Gropp, Parallel Multilevel Methods for Elliptic Partial Differential Equations. Cambridge University Press, Cambrige (1996). Zbl0857.65126MR1410757
  20. [20] P. Le Tallec, Domain decomposition methods in computational mechanics, in Computational Mechanics Advances, J.T. Oden, Ed., North-Holland 1 (1994) 121–220. Zbl0802.73079
  21. [21] R.S. Tuminaro and C. Tong, Parallel smoothed aggregation multigrid: Aggregation strategies on massively parallel machines, in SuperComputing 2000 Proceedings, J. Donnelley, Ed. (2000). 
  22. [22] P. Vanek, M. Brezina and R. Tezaur, Two-grid method for linear elasticity on unstructured meshes. SIAM J. Sci. Comput. 21 (1999) 900–923. Zbl0952.65099
  23. [23] P. Vanek, M. Brezina and J. Mandel, Convergence of algebraic multigrid based on smoothed aggregation. Numer. Math. 88 (2001) 559–579. Zbl0992.65139

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.