×

FLUPS: a Fourier-based library of unbounded Poisson solvers. (English) Zbl 1464.35063

Summary: A Fourier-based library of unbounded Poisson solvers (FLUPS) for 2D and 3D homogeneous distributed grids is presented. It is designed to handle every possible combination of periodic, symmetric, semi-unbounded, and fully unbounded boundary conditions for the Poisson equation on rectangular domains with uniform resolution. FLUPS leverages a dedicated implementation of 3D Fourier transforms to solve the Poisson equation using Green’s functions in a fast and memory-efficient way. Several Green’s functions are available, optionally with explicit regularization, spectral truncation, or using lattice Green’s functions, and provide verified convergence orders from 2 to spectral-like. The algorithm depends on the FFTW library to perform 1D transforms, while message passing interface (MPI) communications enable the required remapping of data in memory. For the latter operation, a first available implementation resorts to the standard all-to-all routines. A second implementation, featuring non-blocking and persistent point-to-point communications, is however shown to be more efficient in a majority of cases and especially while taking advantage of the shared memory parallelism with OpenMP. The scalability of the algorithm, aimed at massively parallel architectures, is demonstrated up to 73720 cores. The results obtained with three different supercomputers show that the weak efficiency remains above 40% and the strong efficiency above 30% when the number of cores is multiplied by 16, for typical problems. These figures are slightly better than those expected from a third party 3D fast Fourier transform (FFT) tool, with which a 20% longer execution time was also measured on average. From the outside, the solving procedure is fully automated so that the user benefits from the optimal performances while not having to handle the complexity associated with memory management, data mapping, and Fourier transform computation. The parallel code is available under Apache license 2.0 at github.com/vortexlab-uclouvain/flups.

MSC:

35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
35J08 Green’s functions for elliptic equations
35J25 Boundary value problems for second-order elliptic equations
68N01 General topics in the theory of software
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] A. Alexandrov, M. F. Ionescu, K. E. Schauser, and C. Scheiman, LogGP: Incorporating long messages into the LogGP model for parallel computation, J. Parallel Distributed Comput., 44 (1997), pp. 71-79, https://doi.org/10.1006/jpdc.1997.1346.
[2] C. R. Anderson, High order expanding domain methods for the solution of Poisson’s equation in infinite domains, J. Comput. Phys., 314 (2016), pp. 194-205, https://doi.org/10.1016/j.jcp.2016.02.074. · Zbl 1349.65640
[3] J. C. Bowman and M. Roberts, Adaptive matrix transpose algorithms for distributed multicore processors, in Interdisciplinary Topics in Applied Mathematics, Modeling and Computational Science, Springer, New York, 2015, pp. 97-103. · Zbl 1331.65064
[4] P. Chatelain and P. Koumoutsakos, A Fourier-based elliptic solver for vortical flows with periodic and unbounded directions, J. Comput. Phys., 229 (2010), pp. 2425-2431. · Zbl 1423.76332
[5] P. Chatelain and A. Leonard, Isotropic compact interpolation schemes for particle methods, J. Comput. Phys., 227 (2008), pp. 3244-3259, https://doi.org/10.1016/j.jcp.2007.11.039. · Zbl 1132.76042
[6] A. G. Chatterjee, M. K. Verma, A. Kumar, R. Samtaney, B. Hadri, and R. Khurram, Scaling of a fast Fourier transform and a pseudo-spectral fluid solver up to 196608 cores, J. Parallel Distributed Comput., 113 (2018), pp. 77-91, https://doi.org/10.1016/j.jpdc.2017.10.014.
[7] P. Costa, A FFT-based finite-difference solver for massively-parallel direct numerical simulations of turbulent flows, Comput. Math. Appl., 76 (2018), pp. 1853-1862, https://doi.org/10.1016/j.camwa.2018.07.034. · Zbl 1442.65156
[8] L. Dalcin, M. Mortensen, and D. E. Keyes, Fast parallel multidimensional FFT using advanced MPI, J. Parallel Distributed Comput., 128 (2019), pp. 137-150, https://doi.org/10.1016/j.jpdc.2019.02.006.
[9] B. Dorschner, K. Yu, G. Mengaldo, and T. Colonius, A fast multi-resolution lattice Green’s function method for elliptic difference equations, J. Comput. Phys., 407 (2020), 109270. · Zbl 07504725
[10] M. Frigo and S. G. Johnson, The design and implementation of FFTW3, Proc. IEEE, 93 (2005), pp. 216-231.
[11] V. Fuka, POISFFT-a free parallel fast Poisson solver, Appl. Math. Comput., 267 (2015), pp. 356-364, https://doi.org/10.1016/j.amc.2015.03.011. · Zbl 1410.65417
[12] A. Gholami, D. Malhotra, H. Sundar, and G. Biros, FFT, FMM, or multigrid? A comparative study of state-of-the-art Poisson solvers for uniform and nonuniform grids in the unit cube, SIAM J. Sci. Comput., 38 (2016), pp. C280-C306, https://doi.org/10.1137/15M1010798. · Zbl 1369.65138
[13] T. Gillis, G. Winckelmans, and P. Chatelain, Fast immersed interface Poisson solver for 3D unbounded problems around arbitrary geometries, J. Comput. Phys., 354 (2018), pp. 403-416, https://doi.org/10.1016/j.jcp.2017.10.042. · Zbl 1380.65410
[14] A. Gillman and P. Martinsson, Fast and accurate numerical methods for solving elliptic difference equations defined on lattices, J. Comput. Phys., 229 (2010), pp. 9026-9041, https://doi.org/10.1016/j.jcp.2010.07.024. · Zbl 1203.65280
[15] A. Gillman and P. Martinsson, A fast solver for Poisson problems on infinite regular lattices, J. Comput. Appl. Math., 258 (2014), pp. 42-56, https://doi.org/10.1016/j.cam.2013.09.003. · Zbl 1294.65104
[16] L. Greengard, S. Jiang, and Y. Zhang, The anisotropic truncated kernel method for convolution with free-space Green’s functions, SIAM J. Sci. Comput., 40 (2018), pp. A3733-A3754, https://doi.org/10.1137/18M1184497. · Zbl 1481.65262
[17] L. Greengard and V. Rokhlin, A fast algorithm for particle simulations, J. Comput. Phys., 135 (1997), pp. 280-292. · Zbl 0898.70002
[18] M. Hejlesen, J. Rasmussen, P. Chatelain, and J. Walther, A high order solver for the unbounded Poisson equation, J. Comput. Phys., 252 (2013), pp. 458-467, https://doi.org/10.1016/j.jcp.2013.05.050. · Zbl 1349.65687
[19] M. M. Hejlesen, G. Winckelmans, and J. H. Walther, Non-singular Green’s functions for the unbounded Poisson equation in one, two and three dimensions, Appl. Math. Lett., 89 (2019), pp. 28-34, https://doi.org/10.1016/j.aml.2018.09.012. · Zbl 1414.35056
[20] R. Hockney and J. Eastwood, Computer Simulation Using Particles, Taylor & Francis, Bristol, PA, 1988. · Zbl 0662.76002
[21] R. W. Hockney, A fast direct solution of Poisson’s equation using Fourier analysis, J. ACM, 12 (1965), pp. 95-113. · Zbl 0139.10902
[22] H. Ibeid, L. Olson, and W. Gropp, FFT, FMM, and multigrid on the road to exascale: Performance challenges and opportunities, J. Parallel Distributed Comput., 136 (2020), pp. 63-74.
[23] J. L. Jodra, I. Gurrutxaga, J. Muguerza, and A. Yera, Solving Poisson’s equation using FFT in a GPU cluster, J. Parallel Distributed Comput., 102 (2017), pp. 28-36, https://doi.org/10.1016/j.jpdc.2016.09.004.
[24] S. Liska and T. Colonius, A parallel fast multipole method for elliptic difference equations, J. Comput. Phys., 278 (2014), pp. 76-91, https://doi.org/10.1016/j.jcp.2014.07.048. · Zbl 1349.65700
[25] P.-G. Martinsson and G. J. Rodin, Asymptotic expansion of lattice Green’s function, R. Soc. Lond. Proc. Ser. A Math. Phys. Eng. Sci., 458 (2002), pp. 2609-2622. · Zbl 1022.39022
[26] D. Pekurovsky, P3DFFT: A framework for parallel computations of Fourier transforms in three dimensions, SIAM J. Sci. Comput., 34 (2012), pp. C192-C209, https://doi.org/10.1137/11082748X. · Zbl 1253.65205
[27] M. Pippig, PFFT: An extension of FFTW to massively parallel architectures, SIAM J. Sci. Comput., 35 (2013), pp. C213-C236, https://doi.org/10.1137/120885887. · Zbl 1275.65098
[28] J. Qiang, A fast parallel 3D Poisson solver with longitudinal periodic and transverse open boundary conditions for space-charge simulations, Comput. Phys. Commun., 219 (2017), pp. 255-260, https://doi.org/10.1016/j.cpc.2017.06.002. · Zbl 1411.65154
[29] I. F. Sbalzarini, J. H. Walther, B. Polasek, P. Chatelain, M. Bergdorf, S. E. Hieber, E. M. Kotsalis, and P. Koumoutsakos, A software framework for the portable parallelization of particle-mesh simulations, in European Conference on Parallel Processing (Dresden, Germany), Springer, New York, 2006, pp. 730-739.
[30] H. J. Spietz, M. M. Hejlesen, and J. H. Walther, A regularization method for solving the Poisson equation for mixed unbounded-periodic domains, J. Comput. Phys., 356 (2018), pp. 439-447, https://doi.org/10.1016/j.jcp.2017.12.018. · Zbl 1380.65411
[31] A. Sunderland, S. Pickles, M. Nikolic, A. Jovic, J. Jakic, V. Slavnic, I. Girotto, P. Nash, and M. Lysaght, An Analysis of FFT Performance in PRACE Application Codes, Tech. report, PRACE, Brussels, Belgium, 2012.
[32] U. Trottenberg, C. Oosterlee, and A. Schuller, Multigrid, Academic Press, New York, 2000.
[33] F. Vico, L. Greengard, and M. Ferrando, Fast convolution with free-space Green’s functions, J. Comput. Phys., 323 (2016), pp. 191-203, https://doi.org/10.1016/j.jcp.2016.07.028. · Zbl 1415.65269
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.