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

A parallel algorithm for solving 2D Poisson’s equation in the context of nonstationary problems

Authors

  • N.V. Snytnikov

Keywords:

Poisson’s equation
Dirichlet problem
domain decomposition
gravitational potential
stellar dynamics
parallel programming
scalability of algorithms

Abstract

A new parallel method to solve the Dirichlet problem for Poisson’s equation in the context of nonstationary problems of mathematical physics is proposed. This method is based on a decomposition of a rectangular Cartesian domain in one direction, on a direct method of solving Poisson’s equation in each subdomain, and on the coupling of the subdomains using a fast procedure for evaluating a single layer potential. A number of test experiments conducted on supercomputers installed at Joint Supercomputing Center of Russian Academy of Sciences and at Siberian Supercomputing Center show a good weak and strong scalability of the parallel algorithm.

New computational technologies

Downloads

Published

2015-02-03

Issue

Vol. 16 (2015): Issue 1.

Section

Section 1. Numerical methods and applications

Author Biography

N.V. Snytnikov

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

References

  1. V. N. Snytnikov, V. A. Vshivkov, E. A. Kuksheva, et al., “Three-Dimensional Numerical Simulation of a Nonstationary Gravitating N-Body System with Gas,” Pis’ma v Astron. Zh. 30 (2), 146-160 (2004) [Astron. Lett. 30 (2), 124-137 (2004)].
  2. I. R. King, An Introduction to Classical Stellar Dynamics (Univ. California, Berkeley, 1994; Editorial URSS, Moscow, 2002).
  3. Yu. A. Berezin and V. A. Vshivkov, The Particle Method in the Dynamics of a Rarefied Plasma (Nauka, Novosibirsk, 1980) [in Russian].
  4. R. W. Hockney and J. W. Eastwood, Computer Simulation Using Particles (McGraw-Hill, New York, 1981).
  5. R. W. Hockney, “Gravitational Experiments with a Cylindrical Galaxy,” Astrophys. J. 150, 797-806 (1967).
  6. V. A. Vshivkov, V. N. Snytnikov, and N. V. Snytnikov, “Simulation of the Three-Dimensional Dynamics of Matter in the Gravitational Field Using Multiprocessor Computers,” Vychisl. Tekhnol. 11 (2), 15-27 (2006).
  7. R. A. James, “The Solution of Poisson’s Equation for Isolated Source Distributions,” J. Comput. Phys. 25 (2), 71-93 (1977).
  8. V. A. Vshivkov and A. V. Snytnikov, “Development of an Efficient Parallel Poisson Equation Solver for the Simulation of Protoplanetary Disk Evolution,” Vychisl. Metody Programm. 10, 116-122 (2009).
  9. Yu. M. Laevsky and A. M. Matsokin, “Decomposition Methods for the Solution to Elliptic and Parabolic Boundary Value Problems,” Sib. Zh. Vychisl. Math. 2 (4), 361-372 (1999).
  10. V. P. Il’in, Finite Difference and Finite Volume Methods for Elliptic Equations (Sobolev Inst. Math., Novosibirsk, 2000) [in Russian].
  11. C. R. Anderson, “Domain Decomposition Techniques and the Solution of Poisson’s Equation in Infinite Domains,” in Domain Decomposition Methods (SIAM Press, Philadelphia, 1989), pp. 129-139.
  12. G. T. Balls and P. Colella, “A Finite Difference Domain Decomposition Method Using Local Corrections for the Solution of Poisson’s Equation,” J. Comput. Phys. 180 (1), 25-53 (2002).
  13. P. McCorquodale, P. Colella, G. T. Balls, and S. B. Baden, “A Local Corrections Algorithm for Solving Poisson’s Equation in Three Dimensions,” Commun. Appl. Math. Comput. Sci. 2 (1), 57-81 (2007).
  14. J. Huang and L. Greengard, “A Fast Direct Solver for Elliptic Partial Differential Equations on Adaptively Refined Meshes,” SIAM J. Sci. Comput. 21 (4), 1551-1566 (1999).
  15. P. M. Ricker, “A Direct Multigrid Poisson Solver for Oct-Tree Adaptive Meshes,” Astrophys. J. Suppl. Ser. 176 (1), 293-300 (2008).
  16. A. V. Terekhov, “Parallel Dichotomy Algorithm for Solving Tridiagonal System of Linear Equations with Multiple Right-Hand Sides,” Parallel Comput. 36 (8), 423-438 (2010).
  17. A. V. Terekhov, “A Fast Parallel Algorithm for Solving Block-Tridiagonal Systems of Linear Equations Including the Domain Decomposition Method,” Parallel Comput. 39 (6/7), 245-258 (2013).
  18. N. N. Yanenko, A. N. Konovalov, A. N. Bugrov, and G. V. Shustov, “On Organization of Parallel Computations and Parallelization of the Tridiagonal Matrix Algorithm,” in Numerical Methods of Continuum Mechanics (Inst. Theor. Appl. Mech., Novosibirsk, 1978), Vol. 9, Issue 7, pp. 139-146.
  19. O. Ayala and L.-P. Wang, “Parallel Implementation and Scalability Analysis of 3D Fast Fourier Transform Using 2D Domain Decomposition,” Parallel Comput. 39 (1), 58-77 (2013).
  20. T. V. T. Duy and T. Ozaki, “A Decomposition Method with Minimum Communication Amount for Parallelization of Multi-Dimensional FFTs,” Comput. Phys. Commun. 185 (1), 153-164 (2014).
  21. V. Springel, N. Yoshida, and S. D. M. White, “GADGET: A Code for Collisionless and Gasdynamical Cosmological Simulation,” New Astr. 6 (2), 79-117 (2001).
  22. A. Dubey, K. Antypas, M. K. Ganapathy, et al., “Extensible Component-Based Architecture for FLASH, a Massively Parallel, Multiphysics Simulation Code,” Parallel Comput. 35 (10/11), 512-522 (2009).
  23. IntelRMath Kernel Library 10.0: Overview.
    https://software.intel.com/en-us/intel-mkl . Cited January 8, 2015.
  24. A. A. Samarskii and E. S. Nikolaev, Numerical Methods for Grid Equations (Nauka, Moscow, 1978; Birkh854user, Basel, 1989).
  25. M. Frigo and S. G. Johnson, “FFTW software,”
    http://www.fftw.org . Cited January 8, 2015.