Strip Decomposition Parallelization of Fast Direct Poisson Solver on a 3D Cartesian Staggered Grid

Authors: Minh Vuong Pham, Frédéric Plourde, Son Doan Kim

Abstract:

A strip domain decomposition parallel algorithm for fast direct Poisson solver is presented on a 3D Cartesian staggered grid. The parallel algorithm follows the principles of sequential algorithm for fast direct Poisson solver. Both Dirichlet and Neumann boundary conditions are addressed. Several test cases are likewise addressed in order to shed light on accuracy and efficiency in the strip domain parallelization algorithm. Actually the current implementation shows a very high efficiency when dealing with a large grid mesh up to 3.6 * 10⁹ under massive parallel approach, which explicitly demonstrates that the proposed algorithm is ready for massive parallel computing.

Keywords: Strip-decomposition, parallelization, fast directpoisson solver.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1080662

References:

[1] R. Löhner, C. Yang, J, J. Cebral, F. Camelli, O. Soto and J. Waltz, "Improving the speed and accuracy of projection-type incompressible flow solvers", Comput. Methods Appl. Mech. Engrg, vol. 195, 2006, pp. 3087-3109.
[2] R. W. Hockney, "A fast direct solution of Poisson equation using Fourier analysis", J. Assoc. Comput. Mach., vol. 8, 1965, pp. 95-113.
[3] J. Cooley and J. Tukey, "An algorithm for the machine calculation of complex Fourier series", Math. Comput., vol. 19, 1965, pp. 297-301.
[4] A. McKenney, L. Greengard and A. Mayo, "A fast Poisson solver for complex geometries", J. Comput. Phys., vol. 118, 1995, pp. 348-355.
[5] U. Schumann and R. A. Sweet, "Fast Fourier transforms for direct solution of Poisson's equation with staggered boundary conditions", J. Comput. Phys., vol. 75, 1988, pp. 123-127.
[6] C. Temperton, "On the FACR(l) algorithm for the discrete Poisson equation", J. Comput. Phys., vol. 34, 1980, pp. 314-329.
[7] E. Braverman, M. Israeli and A. Averbuch, "A fast solver for a 3D Helmholtz equation", SIAM J. Sci. Comput., vol. 20(6), 1999, pp. 2237- 2260.
[8] G. H. Golub, L. C. Huang, H. Simon and W. P. Tang, "A fast Poisson solver for the finite difference solution of the incompressible Navier- Stokes enquations", SIAM J. Sci. Comput., vol. 19(5), 1998, pp. 1606- 1624.
[9] J. C. Adams and P. N. Swarztrauber, "SPHEREPACK 3.0: A model development facility", Monthly Weather Review, vol. 127, 1999, pp. 1872-1878.
[10] P. N. Swarztrauber and R. A. Sweet, "Vector and parallel methods for the direct solution of Poisson's equation", J. Comput. and Appl. Math., vol. 27, 1989, pp. 241-163.
[11] P. N. Swarztrauber, "The vector multiprocessor", Int. J. High Speed Comput., vol. 11, 2000, pp. 1-18.
[12] U. Schumann and M. Strietzel, "Parallel solution of Tridiagonal systems for the Poisson equation", J. Sci. Comput., vol. 10, 1995, pp. 181-190.
[13] T. F. Chan and D. C. Resasco, "A domain-decomposed fast Poisson solver on a rectangle", SIAM J. Sci. Stat. Comput., vol. 8, 1987, pp. 27- 42.
[14] T. Hoshino, Y. Sato and Y. Asamoto, "Parallel Poisson solver FAGECRimplementation and performance evaluation on PAX computer", J. Info. Proc., vol. 12(1), 1988, pp. 20-26.
[15] S. Ghanemi, "A domain decomposition method for Helmholtz scattering problems", Ninth. Int. conf. Dom. Demcomp. Meth., 1998, pp. 105-112.
[16] J. -Y. Lee and K. Jeong, "A parallel Poisson solver using the fast multipole method on networks of workstations", Comput. Math. Appl., vol. 36, 1998, pp. 47-61.
[17] P. Grandclément, S. Bonazzola, E. Gourgoulhon and J. -A. Marck, "A multidomain spectral method for scalar and vectorial Poisson equations with noncompact sources", J. Comput. Phys., 170, 2001, pp. 231-260.
[18] M. Israeli, L. Vozovoi and A. Averbuch, "Parallelizing implicit algorithm fo time-dependent problems by parabolic domain decomposition", J. Sci. Comput,. Vol. 8(2), 1993, pp. 151-166.
[19] W. Briggs, L. Hart, R. A. Sweet and A. O'Gallagher, "Multiprocessor FFT methods", SIAM J. Sci. Stat. Comput., vol. 8, 1987, pp. 27.
[20] P. N. Swarztrauber, "Multiprocessor FFTs", Parallel Computing, vol. 5, 1987, pp. 197-210.
[21] P. N. Swarztrauber and R. A. Sweet, "The Fourier and cyclic reduction methods for solving Poisson's equation", In: Handbook of Fluid Dynamics and Fluid Machinery, J. A. Schetz and A. E. Fuhs, eds., John Wiley and Sons, New York, NY, 1996.
[22] L. Borges and P. Daripa, "A fast parallel algorithm for the Poisson equation on a disk", J. Comput. Phys., vol. 169, 2001, pp. 151-192.
[23] J. Yang and E. Balaras, "An embedded-boundary formulation for largeeddy simulation of turbulent flows interacting with moving boundaries", J. Comput. Phys., vol. 215(1), 2006, pp. 12-40.
[24] E. Balaras, "Modeling complex boundaries using an external force field on fixed Cartesian grids in large-eddy simulations", Computers & Fluids, vol. 33(3), 2004, pp. 375-404.
[25] E. A. Fadlun, R. Verzicco, P. Orlandi and J. Mohd-Yusof, "Combined Immersed-Boundary Finite-Difference Methods for Three-Dimensional Complex Flow Simulations", J. Comput. Phys., vol. 161(1), 2000, pp. 35- 60.
[26] P. Pacheco, "Parallel programming with MPI", Morgan Kaufmann, San Francisco, CA, 1997.
[27] G. Sköllermo, "A Fourier method for the numerical solution of Poisson's equation", Math. Comput., vol. 29, 1975, pp. 697.