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

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

Authors

  • V.M. Volokhov
  • S.I. Martynenko
  • P.D. Toktaliev
  • L.S. Yanovskiy
  • A.V. Volokhov

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.

New computational technologies

Downloads

Published

2016-03-07

Issue

Vol. 17 (2016): Issue 1.

Section

Section 1. Numerical methods and applications

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