Parallel Algorithms Analysis for Symmetrized Triangular Methods for Solving Grid Elliptic Equations
DOI:
https://doi.org/10.14529/cmse260301Keywords:
grid equations, Poisson equation, iterative methods, successive over-relaxation method, SSOR, parallel algorithms, domain decomposition, OpenMP, speedupAbstract
The development of efficient computational methods for modeling complex physical processes in coastal zones, such as the Azov Sea, requires solving large systems of grid elliptic equations. This work presents an analysis of parallel algorithms for symmetrized triangular methods for solving these equations. The aim of the research is the development and scalability investigation of parallel implementations of the Symmetric Successive Over-Relaxation (SSOR) method, targeted at shared-memory architectures. Based on a theoretical analysis of the SSOR method and its properties as a preconditioner for the conjugate gradient method, a parallel algorithm is proposed. This algorithm utilizes domain decomposition and a diagonal (wavefront) traversal order of subdomains to minimize thread idle time. For the Poisson equation Dirichlet problem on a square domain, a series of numerical experiments was conducted. These experiments allow for assessing the influence of the relaxation parameter ω on the convergence rate, as well as determining the speedup of the parallel implementation on various grids. The obtained results demonstrate the high efficiency of the proposed approach with a moderate number of threads and confirm the promise of using symmetrized methods as a basis for constructing parallel preconditioners in ecological modeling tasks.
References
Kovaleva G.V. The problem of water "bloom" in the Sea of Azov. Proceedings of the Southern Scientific Centre of the Russian Academy of Sciences. 2020. Vol. 8. P. 122–148. (in Russian) DOI: 10.23885/1993-6621-2020-8-122-148.
Matishov G.G., Kulygin V.V., Valov G.V., et al. Modern problems of hydrophysical processes modeling (on the example of the Sea of Azov). Science of the South of Russia. 2020. Vol. 16, no. 1. P. 36–44. (in Russian) DOI: 10.7868/S25000640200105.
Darian H.M. The optimal relaxation parameter for the SOR method applied to the Poisson equation on rectangular grids with different types of boundary conditions. Journal of Computational and Theoretical Transport. 2026. Vol. 55, no. 1. P. 26–54. DOI: 10.1080/23324309.2025.2583184.
Axelsson O. A generalized SSOR method. BIT Numerical Mathematics. 1972. Vol. 12. P. 443–467. DOI: 10.1007/BF01932955.
Chen C.-S., Wang W., Li Y.-C., et al. Dynamical Optimal Values of Parameters in the SSOR, AOR, and SAOR Testing Using Poisson Linear Equations. Mathematics. 2023. Vol. 11, no. 18. P. 3828. DOI: 10.3390/math11183828.
Butyugin D.S. Parallel SSOR preconditioner for solving frequency-domain electromagnetism problems. Parallel Computational Technologies (PCT’2011): Proceedings of the International Scientific Conference, Moscow, Russia, March 28 – April 1, 2011 / ed. by L.B. Sokolinsky, K.S. Pan. Moscow: Publishing of the South Ural State University, 2011. P. 49–59. (in Russian) EDN: TBLWGZ.
Sukhinov A.I., Chistyakov A.E., Nikitina A.V., et al. Construction of parallel algorithms for modeling hydrodynamic processes in the Sea of Azov based on hybrid MPI+OpenMP technology. Computational Continuum Mechanics. 2023. Vol. 16, no. 1. P. 17–35. (in Russian) DOI: 10.7242/1999-6691/2023.16.1.2.
Sukhinov A.I., Litvinov V.N., Chistyakov A.E., et al. Solving Grid Equations Using the Alternating-Triangular Method on a Graphics Accelerator. Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering. 2023. Vol. 12, no. 2. P. 78–92. DOI: 10.14529/cmse230204.
Sidoryakina V.V., Solomakha D.A. Symmetrized Versions of the Seidel and Upper Relaxation Methods for Solving Two-Dimensional Difference Problems of Elliptic Type. Computational Mathematics and Information Technologies. 2023. Vol. 7, no. 3. P. 12–19. (in Russian) DOI: 10.23947/2587-8999-2023-7-3-12-19.
Chetverushkin B.N., Yakobovskiy M.V., Kornilina M.A., Semenova A.V. Numerical Algorithms for HPC Systems and Fault Tolerance. Parallel Computational Technologies. Vol. 1063 / ed. by L. Sokolinsky, M. Zymbler. Cham: Springer, 2019. P. 34–44. Communications in Computer and Information Science. DOI: 10.1007/978-3-030-28163-2_3.
Sukhinov A.I., Chistyakov A.E., Alekseenko E.V. Numerical realization of three-dimensional model of hydrodynamics for shallow water basins on high-performance system. Mathematical Models and Computer Simulations. 2012. Vol. 4, no. 5. P. 427–441. DOI: 10.1134/S2070048212050083.
