Study of Graphics Accelerators Performance for Numerical Solution of the Poisson Equation Using the Chebyshev Method

Sergey V. Polyakov; Marina A. Kornilina; Tatiana A. Kudryashova

doi:10.14529/jsfi260202

Authors

Sergey V. Polyakov Keldysh Institute of Applied Mathematics of RAS, Moscow, Russian Federation https://orcid.org/0000-0003-1859-9034
Marina A. Kornilina Keldysh Institute of Applied Mathematics of RAS, Moscow, Russian Federation https://orcid.org/0000-0002-7527-0238
Tatiana A. Kudryashova Keldysh Institute of Applied Mathematics of RAS, Moscow, Russian Federation https://orcid.org/0000-0001-5128-008X

DOI:

https://doi.org/10.14529/jsfi260202

Keywords:

Dirichlet boundary problem for Poisson equation, cross difference scheme, Chebyshev preconditioned method, parallel implementation for central and graphics processor units

Abstract

The problem of the efficient numerical solution of boundary value problems for elliptic equations on high-performance computing systems is discussed. In the context of this problem, the use of a special Chebyshev iterative method to solve such problems by the multi-core central processors and graphics accelerators is analyzed. One of the objective functions of such analysis is to compare the time of solving an elliptic boundary value problem by one node with several central processors and one graphics accelerator. The motivation for this consideration is that in many practical applications, the numerical solution of an elliptic problem significantly slows down the overall algorithm. Taking this circumstance into account, as an example, a two-dimensional Dirichlet boundary value problem for the Poisson equation with constant and variable coefficients is considered. Its solution is based on the well-known "cross" scheme on the most detailed Cartesian grid. For this statement, a modified Chebyshev iterative algorithm is proposed. Such approach significantly reduces the requirements to the used RAM. A parallel software implementation of the algorithm, designed for both central processing units (CPUs) and graphics accelerators (GPUs), is examined. The study investigates the algorithm's convergence and the performance of the used computing systems. It analyzes their dependence on the dimension of the grid problem and other parameters. Numerical experiments are used to determine the limits of the algorithm's applicability and to discuss the efficiency of its implementation on CPUs and GPUs.

References

Keldysh, M.V.: On the solvability and stability of the Dirichlet problem. Advances in Mathematical Sciences (8), 171–231 (1941). (in Russian)

Eymard, R., Gallouet, T.R., Herbin, R.: The finite volume method. Handbook of Numerical Analysis 7, 713–1020 (2000). https://doi.org/10.1016/S1570-8659(00)07005-8

Zienkiewicz, O.C., Taylor, R.L., Zhu, J.Z.: The finite element method: Its basis and fundamentals. Butterworth-Heinemann, Oxford (2013). https://doi.org/10.1016/C2009-0-24909-9

Axelsson, O.: A generalazed SSOR method. BIT 12, 443–467 (1972). https://doi.org/10.1007/BF01932955

Marchuk, G.I., Kuznetsov, Yu.A.: Iterative methods and quadratic functionals. Nauka. Sib. otdel., Novosibirsk (1972). (in Russian)

Bakhvalov, N.S.: Numerical methods: Analysis, algebra, ordinary differential equations. MIR Publishers, Moscow (1977).

Meijerink, J.A., van der Vorst, H.A.: An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix. Math. Comp. 31(137), 148–162 (1977). https://doi.org/10.1090/S0025-5718-1977-0438681-4

Gustafsson, I.: A class of first order factorization methods. BIT 18, 142–156 (1978). https://doi.org/10.1007/BF01931691

Ortega, J.M.: Introduction to parallel and vector solution of linear systems. Plenum Press, New York (1988). https://doi.org/10.1007/978-1-4899-2112-3

Samarskii, A.A., Nikolaev, E.S.: Numerical methods for grid equations. Birkhauser Verlag, Basel-Boston-Berlin (1989). https://doi.org/10.1007/978-3-0348-9272-8

Il’in, V.P.: Iterative incomplete factorization methods. World Sci. Publ., Singapore (1992). https://doi.org/10.1142/1677

Van der Vorst, H.A.: Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems. SIAM Journal on Scientific Computing 13, 631–644 (1992). https://doi.org/10.1137/0913035

Axelsson, O.: Iterative solution methods. Cambridge Univ. Press, Cambridge (1994). https://doi.org/10.1017/CBO9780511624100

Kaporin, I.E.: New convergence results and preconditioning strategies for the conjugate gradient method. J. Numer. Linear. Algebra Applic. 1(2), 179–210 (1994). https://doi.org/10.1002/nla.1680010208

Kaporin, I.E.: High quality preconditioning of a general symmetric positive definite matrix based on its UTU+UTR+RTU-decomposition. J. Numer. Linear. Algebra Applic. 5(6), 483–509 (1998). https://doi.org/10.1002/(SICI)1099-1506(199811/12)5:6<483::AID-NLA156>3.0.CO;2-7

Axelsson, O., Kaporin, I.: On the sublinear and superlinear rate of convergence of conjugate gradient methods. Numerical Algorithms (25), 1–22 (2000). https://doi.org/10.1023/A:1016694031362

Milyukova, O.Yu.: Parallel approximate factorization method for solving discrete elliptic equations. Parallel Computing 27(10), 1365–1379 (2001). https://doi.org/10.1016/S0167-8191(01)00092-8

Higham, N.J.: Accuracy and stability of numerical algorithms. SIAM, Philadelphia (2002). http://doi.org/10.1137/1.9780898718027

Saad, Y.: Iterative methods for sparse linear systems, 2nd ed. SIAM, Philadelphia (2003). http://doi.org/10.1137/1.9780898718003

Van der Vorst, H.A.: Iterative Krylov methods for large linear systems. Cambridge Univ. Press, Cambridge (2003). https://doi.org/10.1017/CBO9780511615115.015

Il’in, V.P.: Finite element methods and technologies. ICM&MG SBRAS Publ., Novosibirsk, (2007). (in Russian)

Knight, P.: The Sinkhorn-Knopp algorithm: convergence and applications. SIAM J. Matrix. Anal. Appl. 30(1), 261–275 (2008). https://doi.org/10.1137/060659624

Walkert, H.F., Ni, P.: Anderson acceleration for fixed-point iterations. SIAM J. on Num. Analysis 49(4), 1715–1735 (2011). https://doi.org/10.1137/10078356X

Liesen, J., Strakos, Z.: Krylov subspace methods, principles and analysis. Oxford Univ. Press, Oxford (2013). https://doi.org/10.1093/acprof:oso/9780199655410.001.0001

Elman, H.C., Silvester, D.J., Wathen, A.J.: Finite elements and fast iterative solvers: with applications in incompressible fluid dynamics. Numerical mathematics and scientific computation. 2nd ed. Oxford Univ. Press, Oxford (2014). https://doi.org/10.1093/acprof:oso/9780199678792.001.0001

Olshanskii, M.A., Tyrtyshnikov, E.E.: Iterative methods for linear systems theory and applications. SIAM, Philadelphia (2014). https://doi.org/10.1137/1.9781611973464

Pratara, P.P., Suryanarayana, P., Pask, J.E.: Anderson acceleration of the Jacobi iterative method. An efficient alternative to Krylov methods for large, sparse linear systems. J. Comput. Phys. 306, 43–54 (2016). https://doi.org/10.1016/j.jcp.2015.11.018

Vabishchevich, P.N., Zakharov, P.E.: Alternating triangular schemes for convection-diffusion problems. Comput. Math. Math. Phys. 56(4), 576–592 (2016). https://doi.org/10.7868/S0044466916040165

Anzt, H., Huckle, T.K., Brackle, J., Dongarra, J.: Incomplete sparse approximate inverses for parallel preconditioning. Parallel Computing 71, 1–22 (2018). https://doi.org/10.1016/j.parco.2017.10.003

Vabishchevich, P.N.: Alternating triangular schemes for second-order evolution equations. Comput. Math. Math. Phys. 59(2), 266–274 (2019). https://doi.org/10.1134/S0965542519020155

Fedorenko, R.P.: Relaxation method for solving difference elliptic equations. Zh. Vych. Matem. i Matem. Fiz. 1(5), 922–927 (1961). (in Russian)

Brandt, A.: Guide to multigrid development. In: Hackbusch, W., Trottenberg, U. (eds.) Multigrid Methods. Lect. Notes in Matem., vol. 960., pp. 220–312. Springer, Berlin, Heidelberg (1982). https://doi.org/10.1007/BFb0069930

Xu, J., Zikatanov, L.: Algebraic multigrid methods. Acta Numerica, 26, 591–721 (2017). https://doi.org/10.1017/S0962492917000083

Il’in, V.P.: Iterative preconditioned methods in Krylov spaces: trends of the 21st Century. Comput. Math. Math. Phys. 61(11), 1750–1775 (2021). https://doi.org/10.1134/S0965542521110099

Milyukova, O.Yu.: A parallel version of the generalized alternating triangular method for elliptic equations. Comput. Math. Math. Phys. 38(12), 1922–1932 (1998). (in Russian)

Milyukova, O.Yu.: Parallel versions of the alternating triangular method for solving three-dimensional elliptic equations. Comput. Math. Math. Phys. 42(10), 1472–1481 (2002). (in Russian)

Kaporin, I.E.: Using Chebyshev polynomials and approximate inverse triangular factorizations for preconditioning the conjugate gradient method. Comput. Math. Math. Phys. 52(2), 169–193 (2012). https://doi.org/10.1134/S0965542512020091

Milyukova, O.Yu.: Combination of numerical and structured approaches to the construction of a second-order incomplete triangular factorization in parallel preconditioning methods. Comput. Math. Math. Phys. 56(5), 699–716 (2016). https://doi.org/10.1134/S096554251605016X

Milyukova, O.Yu.: MPI+OpenMP parallel implementation of conjugate gradient method with factored implicit preconditioners. Math. Models Comput. Simul. 14(3), 367–380 (2022). https://doi.org/10.1134/S2070048222030103

Milyukova, O.Yu.: Some ways of parallel implementation of the conjugate gradient method with an implicit factorized preconditioner. Math. Models Comput. Simul. 16(4), 638–653 (2024). https://doi.org/10.1134/S2070048224700285

Open MPI: Open Source High Performance Computing. https://www.open-mpi.org/, accessed: 2026-05-20

Majo, Z., Gross, T.R.: Memory System Performance in a NUMA Multicore Multiprocessor. http://people.inf.ethz.ch/zmajo/publications/11-systor.pdf (2011), accessed: 2026-05-20

Barney, B.: POSIX Threads Programming. https://computing.llnl.gov/tutorials/pthreads/, accessed: 2026-05-20

Specifications – OpenMP. https://www.openmp.org/specifications, accessed: 2026-05-20

Domain Decompositon Methods (DDM). https://www.ddm.org/, accessed: 2026-05-20

OpenCL – The Open Standard for Parallel Programming of Heterogeneous Systems. https://www.khronos.org/opencl/, accessed: 2026-05-20

Kuo, F.-A., Smith, M.R., Hsieh, Ch.-W., et al.: GPU acceleration for general conservation equations and its application to several engineering problems. Computers & Fluids 45(1), 147–154 (2011). https://doi.org/10.1016/j.compfluid.2010.10.007

Niemeyer, K.E.: GPU Laplace solver using optimized red-black Gauss-Seidel with SOR solver. https://github.com/kyleniemeyer/laplace_gpu (2012), accessed: 2026-05-20

Dominguez, J.M., Crespo, A.J.C., Valdez-Balderas, D., et al.: New multi-GPU implementation for smoothed particle hydrodynamics on heterogeneous clusters. Computer Physics Communications 184(8), 1848–1860 (2013). https://doi.org/10.1016/j.cpc.2013.03.008

Phillips, E., Fatica, M.: A CUDA implementation of the high performance conjugate gradient benchmark. In: Jarvis, S., Wright, S., Hammond, S. (eds.) High Performance Computing Systems. Performance Modeling, Benchmarking, and Simulation. PMBS 2014. Lecture Notes in Computer Science, vol. 8966, pp. 68–84. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-17248-4_4

Menshov, I., Pavlukhin, P.: Highly scalable implementation of an implicit matrix-free solver for gas dynamics on GPU-accelerated clusters. J. Supercomput. 73, 631–638 (2017). https://doi.org/10.1007/s11227-016-1800-1

Gorobets, A., Bakhvalov, P.: Heterogeneous CPU+GPU parallelization for high-accuracy scale-resolving simulations of compressible turbulent flows on hybrid supercomputers. Computer Physics Communications 271, 108231 (2022). https://doi.org/10.1016/j.cpc.2021.108231

Gorobets, A.V.: Adapting a scientific CFD code to industrial applications on hybrid supercomputers. Supercomputing Frontiers and Innovations 9(4), 49–54 (2022). https://doi.org/10.14529/jsfi220405

Magomedov, A.R., Gorobets, A.V.: Heterogeneous implementation of preconditioners based on Gauss–Seidel method for sparse block matrices. Computational Mathematics and Modeling 33(4), 438–442 (2022). https://doi.org/10.1007/s10598-023-09585-2

Khrapov, S.S., Agafonnikova, E.O., Khoperskov, A.V.: Prospects for improving computational efficiency of hydrodynamic simulations on supercomputers by increasing the number of GPUs per compute node. Supercomputing Frontiers and Innovations 12(2), 43–59 (2025). https://doi.org/10.14529/jsfi250204