Algebraic-geometric and information structures of domain decomposition methods

Authors

  • Y.L. Gurieva The Institute of Computational Mathematics and Mathematical Geophysics of SB RAS (ICM&MG SB RAS)
  • V.P. Ilyin The Institute of Computational Mathematics and Mathematical Geophysics of SB RAS (ICM&MG SB RAS)
  • D.V. Perevozkin The Institute of Computational Mathematics and Mathematical Geophysics of SB RAS (ICM&MG SB RAS)

DOI:

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

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.

Author Biographies

Y.L. Gurieva

V.P. Ilyin

D.V. Perevozkin

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).

Published

12-04-2016

How to Cite

Гурьева Я., Ильин В., Перевозкин Д. Algebraic-Geometric and Information Structures of Domain Decomposition Methods // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2016. 17. 132-146. doi 10.26089/NumMet.v17r213

Issue

Section

Section 1. Numerical methods and applications