Strip Decomposition Parallelization of Fast Direct Poisson Solver on a 3D Cartesian Staggered Grid
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 * 109 under massive parallel approach, which explicitly demonstrates that the proposed algorithm is ready for massive parallel computing.
[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.
[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.
@article{"International Journal of Engineering, Mathematical and Physical Sciences:62213", author = "Minh Vuong Pham and Frédéric Plourde and Son Doan Kim", title = "Strip Decomposition Parallelization of Fast Direct Poisson Solver on a 3D Cartesian Staggered Grid ", 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 * 109 under massive parallel approach, which explicitly demonstrates that the proposed algorithm is ready for massive parallel computing.
", keywords = "Strip-decomposition, parallelization, fast directpoisson solver.", volume = "1", number = "3", pages = "190-10", }
