DOI: https://doi.org/10.26089/NumMet.v16r115

On acceleration technologies of parallel decomposition methods

Authors

  • Y.L. Gurieva
  • V.P. Ilyin

Keywords:

domain decomposition
additive Schwarz method
reduction algorithms
preconditioned Krylov processes
scalable parallelization
distributed and shared memory
numerical experiments

Abstract

One of the main obstacles to the scalable parallelization of the algebraic decomposition methods for solving large sparse systems of linear algebraic equations consists in slowing the convergence rate of the additive iterative Schwarz algorithm in the Krylov subspaces when the number of subdomains increases. The aim of this paper is a comparative experimental analysis of various ways to accelerate the iterations: a parametrized intersection of subdomains, the usage of interface conditions at the boundaries of adjacent subdomains, and the application of a coarse grid correction (aggregation, or reduction) for the original linear system to build an additional preconditioner. The parallelization of algorithms is performed on two levels by programming tools for the distributed and shared memory. The benchmark linear systems under study are formed using the finite difference approximations of the Dirichlet problem for the diffusion-convection equation with various values of the convection coefficients and on a sequence of condensing grids.

New computational technologies

Downloads

Published

2015-03-28

Issue

Vol. 16 (2015): Issue 1.

Section

Section 1. Numerical methods and applications

Author Biographies

Y.L. Gurieva

The Institute of Computational Mathematics and Mathematical Geophysics of SB RAS (ICM&MG SB RAS)
• Senior Researcher

V.P. Ilyin

The Institute of Computational Mathematics and Mathematical Geophysics of SB RAS (ICM&MG SB RAS)
• Chief Researcher

References

  1. V. P. Il’in, “Parallel Methods and Technologies of Domain Decomposition,” Vestn. South Ural Univ. No. 46, 31-44 (2012).
  2. A. Toselli and O. B. Widlund, Domain Decomposition Methods - Algorithms and Theory (Springer, Heidelberg, 2005).
  3. R. Bridson and C. Greif, “A Multipreconditioned Conjugate Gradient Algorithm,” SIAM J. Matrix Anal. Appl. 27 (4), 1056-1068 (2006).
  4. O. Dubois, M. J. Gander, S. Loisel, et al., “The Optimized Schwarz Method with a Coarse Grid Correction,” SIAM J. Sci. Comput. 34 (1), 421-458 (2012).
  5. Domain Decomposition Methods.
    http://www.ddm.org . Cited February 15, 2015.
  6. V. P. Il’in, Methods of Finite Differences and Finite Volumes for Elliptic Equations (Inst. Comput. Math. Math. Geophys., Novosibirsk, 2000) [in Russian].
  7. A. Chapman and Y. Saad, “Deflated and Augmented Krylov Subspace Techniques,” Numer. Linear Algebra Appl. 4 (1), 43-66 (1997).
  8. D. S. Butyugin, Ya. L. Guryeva, V. P. Il’in, et al., “Parallel Algebraic Solvers Library Krylov,” Vestn. South Ural Univ. 2 (3), 92-105 (2013).
  9. Siberian Supercomputing Center.
    http://www2.sscc.ru . Cited February 15, 2015.
  10. Intel Math Kernel Library.
    https://software.intel.com/en-us/intel-mkl . Cited February 15, 2015.
  11. Y. Saad, Iterative Methods for Sparse Linear Systems (SIAM Press, Philadelphia, 2003).
  12. V. P. Il’in, Methods and Technologies of Finite Elements (Inst. Comput. Math. Math. Geophys., Novosibirsk, 2007) [in Russian].