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

Acceleration of parallel solution of 2D boundary value problems with two-grid preconditioning

Authors

  • Alexander N. Kozyrev
  • Vladimir D. Korneev
  • Victor M. Sveshnikov

Keywords:

boundary value problems
quasi-structured grids
two-grid preconditioning
parallelization
solution acceleration

Abstract

An algorithm for accelerating the solution of boundary value problems on quasi-structured grids is proposed and experimentally studied. The basis of the algorithm is two-grid preconditioning, which is built on a macro-grid, which is an element of a quasi-structured grid. This approach does not require the introduction of additional tools. A series of numerical experiments were carried out, the results of which show acceleration of calculations by 2.5 times without parallelization only due to preconditioning without parallelization and demonstrate super-acceleration during parallelization.

Downloads

Published

2024-05-04

Issue

Vol. 25 (2024): Issue 2.

Section

Methods and algorithms of computational mathematics and their applications

Author Biographies

Alexander N. Kozyrev

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

Vladimir D. Korneev

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

Victor M. Sveshnikov

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

References

  1. A. N. Kozyrev and V. M. Sveshnikov, “On the Construction of Two-Dimensional Local-Modified Quasistructured Grids and Solving on Them Two-Dimensional Boundary Value Problem in the Domains with Curvilinear Boundary,” Vestn. Yuzhn. Ural. Gos. Univ. Ser. Vychisl. Mat. Inf. 6 (2), 5-21 (2017).
  2. V. D. Liseikin, Grid Generation Methods (Springer, Berlin, 1999).
  3. Yu. I. Shokin, N. T. Danaev, G. S. Khakimzyanov, and N. Yu. Shokina, Lectures on Difference Schemes on Moving Grids (KazNU, Almaty, 2008), Part 2 [in Russian].
  4. A. A. Samarskii, The Theory of Difference Schemes (Nauka, Moscow, 1989; CRC Press, Boca Raton, 2001).
    doi 10.1201/9780203908518
  5. O. V. Ushakova, “On the Development of the Variational Approach to the Generation of Optimal Grids (A Review),” Tr. Inst. Mat. Mekh. UrO RAN 29 (2), 217-247 (2023).
    doi 10.21538/0134-4889-2023-29-2-217-247
  6. R. P. Fedorenko, “The Speed of Convergence of One Iterative Process,” Zh. Vichisl. Mat. Mat. Fiz. 4 (3), 559-564 (1964). [USSR Comput. Math. Math. Phys. 4 (3), 227-235 (1964)].
    doi 10.1016/0041-5553(64)90253-8
  7. N. S. Bakhvalov, “On the Convergence of a Relaxation Method with Natural Constraints on the Elliptic Operator,” Zh. Vichisl. Mat. Mat. Fiz. 6 (5), 861-885 (1966). [USSR Comput. Math. Math. Phys. 6 (5), 101-135 (1966)].
    doi 10.1016/0041-5553(66)90118-2
  8. A. Brandt, “Multi-Level Adaptive Solutions to Boundary-Value Problems,” Math. Comp. 31 (138), 333-390 (1977).
  9. W. Hackbusch, Multi-Grid Methods and Applications (Springer, Berlin, 1985).
  10. Yu. V. Vasilevsky and M. A. Olshansky, A Short Course on Multigrid and Domain Decomposition Methods (Mosk. Gos. Univ., Moscow, 2007) [in Russian].
  11. Y. Saad, Iterative Methods for Sparse Linear Systems (SIAM Press, Philadelphia, 2003; Mosk. Gos. Univ., Moscow, 2013).
  12. R. Bank, R. Falgout, T. Jones, et al., “Algebraic Multigrid Domain and Range Decomposition (AMG-DD/AMG-RD),” SIAM J. Sci. Comput. 37 (5), S113-S136 (2015).
    doi 10.1137/140974717
  13. A. Napov and Y. Notay, “An Efficient Multigrid Method for Graph Laplacian Systems II: Robust Aggregation,” SIAM J. Sci. Comput. 39 (5), S379-S403 (2017).
    doi 10.1137/16M1071420
  14. S. K. Godunov, Equations of Mathematical Physics (Nauka, Moscow, 1979) [in Russian].
  15. A. M. Matsokin and S. V. Nepomnyashchikh, “The Schwarz Alternation Method in a Subspace,” Izv. Vyssh. Uchebn. Zaved. Mat. No. 10, 61-66 (1985). [Soviet Math. (Iz. VUZ). 29 (10), 78-84 (1985)].
  16. V. Dolean, P. Jolivet, and F. Nataf, An Introduction to Domain Decomposition Methods: Algorithms, Theory, and Parallel Implementation (SIAM Press, Philadelphia, 2015).
    doi 10.1137/1.9781611974065.fm
  17. A. Quarteroni and A. Valli, Domain Decomposition Methods for Partial Differential Equations (Oxford Univ. Press, Oxford, 1999).
  18. H. Xiang and F. Notaf, “Two-Level Algebraic Domain Decomposition Preconditioners Using Jacobi-Schwarz Smoother and Adaptive Coarse Grid Corrections,” J. Comput. Appl. Math. 261 (1), 1-13 (2014).
    doi 10.1016/j.cam.2013.10.027
  19. Y. Saad and M. H. Schultz, “GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems,” SIAM J. Sci. Stat. Comput. 7 (3), 856-869 (1986).
    doi 10.1137/0907058
  20. V. P. Ilyin, Finite Difference and Finite Volume Methods for Elliptic Equations (Inst. Comput. Math. Math. Geophys., Novosibirsk, 2000) [in Russian].
  21. V. M. Sveshnikov, “Construction of Direct and Iterative Decomposition Methods,” Sib. Zh. Ind. Mat. 12 (3), 99-109 (2009). [J. Appl. Ind. Math. 4 (3), 431-440 (2010)].
    doi 10.1134/S1990478910030166
  22. V. A. Syrovoy, V. M. Sveshnikov, and A. N. Kozyrev, Analytical and Numerical Modeling of Intense Beams of Charged Particles (Inst. Comput. Math. Math. Geophys., Novosibirsk, 2023) [in Russian].
  23. A. N. Kozyrev and V. M. Sveshnikov, “An Experimental Study of the Efficiency of Solving 2D Boundary Value Problems on Subgrids of Quasi-Structured Rectangular Grids,” Sib. Zh. Vych. Mat. 24 (3), 277-288 (2021). [Numer. Anal. Appl. 14 (3), 238-248 (2021).
    doi 10.1134/S1995423921030046]
  24. G. I. Marchuk, Methods of Computational Mathematics (Nauka, Moscow, 1980; Springer, New York, 1982).

License

Copyright (c) 2024 А. Н. Kозырев, В. Д. Корнеев, В. М. Свешников

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.