New approaches to the development of highly efficient parallel algorithms for numerical solution of boundary value problems on structured grids

Authors

  • V.M. Volokhov Institute of Problems of Chemical Physics of RAS
  • S.I. Martynenko Institute of Problems of Chemical Physics of RAS
  • P.D. Toktaliev Institute of Problems of Chemical Physics of RAS
  • L.S. Yanovskiy Institute of Problems of Chemical Physics of RAS
  • A.V. Volokhov Institute of Problems of Chemical Physics of RAS

DOI:

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

Keywords:

parallel computing, boundary value problems, multigrid methods

Abstract

New approaches to the development of highly efficient parallel algorithms for numerical solution of boundary value problems are considered. The previously proposed robust multigrid technique (a single grid version of the Seidel method for solving a large class of applied problems with close-to-optimal computational efforts) is taken as a basic algorithm. Two approaches for the parallelization of computations based on combined and purely geometric preconditioning are studied. Advantages of these approaches compared to traditional methods of constructing parallel algorithms are shown. Several estimates for the parallelism efficiency are proposed.

Author Biographies

V.M. Volokhov

Institute of Problems of Chemical Physics of RAS
• Head of Department

S.I. Martynenko

Institute of Problems of Chemical Physics of RAS
• Engineer

P.D. Toktaliev

Institute of Problems of Chemical Physics of RAS
• Engineer

L.S. Yanovskiy

Institute of Problems of Chemical Physics of RAS
• Head of Department

A.V. Volokhov

Institute of Problems of Chemical Physics of RAS
• Researcher

References

  1. J. M. Ortega, Introduction to Parallel and Vector Solution of Linear Systems (Plenum, New York, 1988; Mir, Moscow, 1991).
  2. R. P. Fedorenko, “A Relaxation Method for Solving Elliptic Difference Equations,” Zh. Vychisl. Mat. Mat. Fiz. 1 (5), 922-927 (1961) [USSR Comput. Math. Math. Phys. 1 (4), 1092-1096 (1962)].
  3. R. P. Fedorenko, “The Speed of Convergence of One Iterative Process,” Zh. Vychisl. Mat. Mat. Fiz. 4 (3), 559-564 (1964) [USSR Comput. Math. Math. Phys. 4 (3), 227-235 (1964)].
  4. N. S. Bakhvalov, “On the Convergence of a Relaxation Method with Natural Constraints on the Elliptic Operator,” Zh. Vychisl. Mat. Mat. Fiz. 6 (5), 861-885 (1966) [USSR Comput. Math. Math. Phys. 6 (5), 101-135 (1966)].
  5. W. Hackbusch, Multi-Grid Methods and Applications (Springer, Berlin, 1985).
  6. M. A. Ol’shanskii, Lectures and Exercises on Multigrid Methods (Fizmatlit, Moscow, 2005) [in Russian].
  7. U. Trottenberg, C. W. Oosterlee, and A. Schüller, Multigrid (Academic, San-Diego, 2001).
  8. S. I. Martynenko, Multigrid Technology: Theory and Applications (Fizmatlit, Moscow, 2015) [in Russian].
  9. V. T. Zhukov, N. D. Novikova, and O. B. Feodoritova, Parallel Multigrid Method for Elliptic Difference Equations. Part I. Main Elements of the Algorithm , Preprint No. 30 (Keldysh Institute of Applied Mathematics, Moscow, 2003) [in Russian].
  10. S. I. Martynenko, “Robust Multigrid Technique for Solving Partial Differential Equations on Structured Grids,” Vychisl. Metody Programm. 1, 83-102 (2000).
  11. S. I. Martynenko, “Parallelization of Robust Multigrid Technique,” Vychisl. Metody Programm. 4, 45-51 (2003).
New computational technologies

Downloads

Published

07-03-2016

How to Cite

Волохов В., Мартыненко С., Токталиев П., Яновский Л., Волохов А. New Approaches to the Development of Highly Efficient Parallel Algorithms for Numerical Solution of Boundary Value Problems on Structured Grids // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2016. 17. 72-80. doi 10.26089/NumMet.v17r108

Issue

Vol. 17 (2016): Issue 1.

Section

Section 1. Numerical methods and applications

Most read articles by the same author(s)