Computational & Technology Resources
an online resource for computational,
engineering & technology publications
Computational Technology Reviews
ISSN 2044-8430
Computational Technology Reviews
Volume 7, 2013
Acceleration of Convergence for Domain Decomposition Methods
L. Berenguer1, T. Dufaud2 and D. Tromeur-Dervout1

1University of Lyon, University Lyon 1, CNRS, Institut Camille-Jordan, Villeurbanne, France
2INRIA Rennes - Bretagne Atlantique, Universitaire de Beaulieu, Rennes, France

Full Bibliographic Reference for this paper
L. Berenguer, T. Dufaud, D. Tromeur-Dervout, "Acceleration of Convergence for Domain Decomposition Methods", Computational Technology Reviews, vol. 7, pp. 1-24, 2013. doi:10.4203/ctr.7.1
Keywords: partial differential equation of elliptic type, Aitken acceleration of convergence, Schwarz domain decomposition, parallel computing, Darcy.

Summary
The Schwarz domain decomposition method [1] is a very attractive numerical method for parallel computing as it needs only to update the boundary conditions on the artificial interfaces generated by domain decomposition. Thus only local communications between the neighbouring sub-domains are required. Nevertheless, the main drawback of this method is its slow rate of convergence which depends of the partial differential problem, the geometry of the sub-domains, and the size of the overlap when overlap is present. The idea of using Aitken acceleration [2] on the classical additive Schwarz DD method was introduced in [3]. These authors have called the corresponding method the Aitken-Schwarz (AS) method.

This review paper is on the Aitken's acceleration of the convergence technique applied to the Schwarz domain decomposition method. It gives the two salient features of the methodology: first the pure linear convergence of the Schwarz domain decomposition method when it applies to a linear system of equations. Second, the building of an approximation space in order to represent the Schwarz iterate solution at the artificial interfaces generated by the domain decomposition. Some properties such as the decrease in absolute value of the solution's coefficients in the approximation space are searched in order to approximate the error operator and to apply the acceleration on a reduced space for saving computing.In [4] the author extends the methodology with an Aitken acceleration based on the singular value decomposition of the solution at the artificial boundary. Then this method becomes totally mesh non dependant, on some a priori criterion based on the singular values decreasing and gives a tool to select the singular vectors involved in the Aitken operator approximation. This allows three-dimensional computation on the linear Darcy equation to be achieved where the permeability field follows a random log normal distribution law [5].

References
[1]
H.A. Schwarz, "Vierteljahresschrift der naturforschenden gesellschaft", Zurich, 15, 272-286, 1870.
[2]
P. Henrici, "Elements of numerical analysis", John Wiley & Sons Inc., New York,1964.
[3]
M. Garbey, D. Tromeur-Dervout, "On some Aitken-like acceleration of the Schwarz method", Internat. J. Numer. Methods Fluids, 40(12), 1493–1513, 2002. doi:10.1002/fld.407
[4]
D. Tromeur-Dervout, "Meshfree Adaptative Aitken-Schwarz Domain Decomposition with application to Darcy Flow", in B.H.V. Topping, P. Ivanyi, (Editors), "Parallel, Distributed and Grid Computing for Engineering", Saxe-Coburg Publications, Stirlingshire, UK, Chapter 11, 217-260, 2009. doi:10.4203/csets.21.11
[5]
L. Berenguer, T. Dufaud, D. Tromeur-Dervout, "Aitken's acceleration of the Schwarz process using singular value decomposition for heterogeneous 3d groundwater flow problems", Computers & Fluids, 2012. doi:10.1016/j.compfluid.2012.01.026

purchase the full-text of this paper (price £20)

go to the next paper
return to the table of contents
return to Computational Technology Reviews
purchase this volume (price £80 +P&P)