Skip to main content
SpringerLink
Log in

Why Restricted Additive Schwarz Converges Faster than Additive Schwarz

  • Published:
BIT Numerical Mathematics Aims and scope Submit manuscript

Abstract

Recently a variant of the additive Schwarz (AS) preconditioner, the restricted additive Schwarz (RAS) preconditioner has been introduced, and numerical experiments showed that RAS converges faster and requires less communication than AS. We show in this paper how RAS, which is defined at the matrix level, can be interpreted as an iteration at the continuous level of the underlying problem. This interpretation reveals why RAS converges faster than classical AS.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

REFERENCES

  1. X. C. Cai, M. Dryja, and M. Sarkis, A restricted additive Schwarz preconditioner with harmonic overlap for symmetric positive definite linear systems, SIAMJ. Sci. Comp., 2002. Submitted.

  2. X.-C. Cai, C. Farhat, and M. Sarkis, A minimum overlap restricted additive Schwarz preconditioner and applications to 3D flow simulations, Contemp. Math., 218 (1998), pp. 479-485.

    Google Scholar 

  3. X.-C. Cai and M. Sarkis, A restricted additive Schwarz preconditioner for general sparse linear systems, SIAM J. Sci. Comput., 21 (1999), pp. 239-247.

    Google Scholar 

  4. T. F. Chan and T. P. Mathew, Domain decomposition algorithms, in Acta Numerica 1994, Cambridge University Press, 1994, pp. 61-143.

  5. H. K. Dahle, T. O. W. Johansen, T. Botnen, and X.-C. Tai, A characteristic domain decomposition method for modeling flow in a coastal aquifier, in P. E. Bjørstad, M. S. Espedal, and D. E. Keyes (eds.), Ninth International Conference on Domain Decomposition Methods, pp. 698-707. ddm.org, 1998.

  6. M. Dryja and O. B. Widlund, Some domain decomposition algorithms for elliptic problems, in L. Hayes and D. Kincaid (eds.), Iterative Methods for Large Linear Systems, Proceeding of the Conference on Iterative Methods for Large Linear Systems held in Austin, Texas, October 19-21, 1988, to celebrate the sixty-fifth birthday of David M. Young, Jr., Academic Press, San Diego, CA, 1989, pp. 273-291.

    Google Scholar 

  7. E. Efstathiou, Study of the Schwarz algorithms: Understanding restricted additive Schwarz, Master's thesis, McGill University, 2003.

  8. A. Frommer and D. B. Szyld, Weighted max norms, splittings, and overlapping additive Schwarz iterations, Numer. Math., 83 (1999), pp. 259-278.

    Google Scholar 

  9. A. Frommer and D. B. Szyld, An algebraic convergence theory for restricted additive Schwarz methods using weighted max norms, SIAM J. Numer. Anal., 39 (2001), pp. 463-479.

    Google Scholar 

  10. G. H. Golub, Convergence property of discretized domain decomposition methods, Personal communication, 2001.

  11. W. Hackbusch, Iterative Solution of Large Sparse Linear Systems of Equations, Springer-Verlag, Berlin, 1994.

    Google Scholar 

  12. P.-L. Lions, On the Schwarz alternating method. I, in R. Glowinski, G. H. Golub, G. A. Meurant, and J. Périaux (eds.), First International Symposium on Domain Decomposition Methods for Partial Differential Equations, SIAM, Philadelphia, PA, 1988, pp. 1-42.

    Google Scholar 

  13. P.-L. Lions, On the Schwarz alternating method. II, in T. Chan, R. Glowinski, J. Périaux, and O. Widlund (eds.), Domain Decomposition Methods, SIAM, Philadelphia, PA, 1989, pp. 47-70.

    Google Scholar 

  14. R. Nabben and D. B. Szyld, Convergence theory of restricted multiplicative Schwarz methods, Technical Report 01-5-17, Temple University, May 2001.

  15. D. P. O'Leary and R. E. White, Multi-splittings of matrices and parallel solution of linear systems, SIAM J. Alg. Disc. Meth., 6 (1985), pp. 630-640.

    Google Scholar 

  16. M. Sarkis and B. Koobus, A scaled and minimun overlap restricted additive Schwarz method with application on aerodynamics, Comp. Meth. Appl. Mech. and Eng., 184 (2000), pp. 391-400.

    Google Scholar 

  17. H. A. Schwarz, Übereinen Grenzübergang durch alternierendes Verfahren, Vierteljahrsschrift der Naturforschenden Gesellschaft in Zürich, 15 (May 1870), pp. 272-286.

    Google Scholar 

  18. B. F. Smith, P. E. Bjørstad, and W. Gropp, Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations, Cambridge University Press, 1996.

  19. X.-C. Tai, A space decomposition method for parabolic equations, Numer. Method for Part. Diff. Equat., 14(1) (1998), pp. 27-46.

    Google Scholar 

  20. X.-C. Tai, T. O. W. Johansen, H. K. Dahle, and M. S. Espedal, A characteristic domain splitting method, in R. Glowinski, J. Périaux, Z.-C. Shi, and O. Widlund (eds.), Domain Decomposition Methods in Science and Engineering, Wiley, 1996, pp. 317-323.

Download references

Authors
  1. Evridiki Efstathiou
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Martin J. Gander
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Efstathiou, E., Gander, M.J. Why Restricted Additive Schwarz Converges Faster than Additive Schwarz. BIT Numerical Mathematics 43, 945–959 (2003). https://doi.org/10.1023/B:BITN.0000014563.33622.1d

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/B:BITN.0000014563.33622.1d

Search

Navigation