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

Algebraic-geometric and information structures of domain decomposition methods

Authors

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

Keywords:

domain decomposition
large linear systems
sparse matrices
data structures
hybrid programming
parallel programming

Abstract

Algebraic, geometric, and informational aspects of parallel decomposition methods are considered to solve large systems of linear equations with sparse matrices arising after approximation of multidimensional boundary value problems on unstructured grids. Algorithms are based on partitioning a grid computational domain into its subdomains with a parameterized value of overlapping and various interface conditions on the adjacent boundaries. Some questions arising in algebraic decomposition of the original matrix are discussed. Various two-level iterative processes are used. They include both preconditioned Krylov methods with a coarse grid correction and the parallel solution of auxiliary subsystems in subdomains by direct or iterative algorithms. Parallelization of algorithms is implemented by means of hybrid programming with separate MPI processes for each subdomain and by multithreaded computations over shared memory in each of the subdomains. Communications between adjacent subdomains are performed on each external iteration via the preliminary creation of some exchange buffers and using non-blocking operations, which makes it possible to combine both the arithmetic operations and data transfer.

New computational technologies

Downloads

Published

2016-04-12

Issue

Vol. 17 (2016): Issue 2.

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

D.V. Perevozkin

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

References

  1. R. Rabenseifner, G. Hager, and G. Jost, “Hybrid MPI and OpenMP Parallel Programming. MPI+OpenMP and Other Models on Clusters of SMP nodes,” Tutorial tut123 at SC13, November 17, 2013, Denver (CO) USA.
    http://openmp.org/sc13/HybridPP_Slides.pdf . Cited April 5, 2016.
  2. V. P. Il’in, “DELAUNAY: A Technological Environment for Grid Generation,” Sib. Zh. Ind. Mat. 16 (2), 83-97 (2013).
  3. Domain Decomposition Methods.
    http://www.ddm.org . Cited April 5, 2016.
  4. A. Toselli and O. B. Widlund, Domain Decomposition Methods: Algorithms and Theory (Springer, Heidelberg, 2005).
  5. Y. L. Gurieva and V. P. Il’in, “On Parallel Computational Technologies of Augmented Domain Decomposition Methods,” in Lecture Notes in Computer Science (Springer, Heidelberg, 2015), Vol. 9251, pp. 35-46.
  6. V. Dolean, P. Jolivet, and F. Nataf, “An Introduction to Domain Decomposition Methods: Algorithms, Theory, and Parallel Implementation,”
    https://hal.archives-ouvertes.fr/cel-01100932v4/document . Cited April 5, 2016.
  7. V. P. Il’in, “Parallel Methods and Technologies of Domain Decomposition,” Vestn. South Ural Univ. Ser. Vychisl. Mat. Inf. No. 46, 31-44 (2012).
  8. I. A. Klimonov, V. D. Korneev, and V. M. Sveshnikov, “Parallelization Technologies for Solving Three-Dimensional Boundary Value Problems on Quasi-Structured Grids Using the CPU+GPU Hybrid Computing Environment,” Vychisl. Metody Programm. 17, 65-71 (2016).
  9. V. P. Il’in and D. V. Perevozkin, “On Some Variants of Domain Decomposition Methods,” Vestn. South Ural Univ. Ser. Vychisl. Mat. Inf. 3 (2), 5-19 (2014).
  10. ParMETIS - Parallel Graph Partitioning and Fill-Reducing Matrix Ordering.
    http://glaros.dtc.umn.edu/gkhome/metis/parmetis/overview . Cited April 5, 2016.
  11. G. Karypis, “METIS - Serial Graph Partitioning and Fill-Reducing Matrix Ordering,”
    http://glaros.dtc.umn.edu/gkhome/metis/metis/overview . Cited April 5, 2016.
  12. S. Pissanetzky, Sparse Matrix Technology (Academic, London, 1984; Mir, Moscow, 1988).
  13. D. S. Butyugin, Y. L. Guryeva, V. P. Il’in, et al., “Parallel Algebraic Solvers Library Krylov,” Vestn. South Ural Univ. Ser. Vychisl. Mat. Inf. 2 (3), 92-105 (2013).