×

An efficient Poisson solver for complex embedded boundary domains using the multi-grid and fast multipole methods. (English) Zbl 1436.65199

Summary: We present an efficient method to solve the Poisson equation in embedded boundary (EB) domains. The original problem is divided into an inhomogeneous problem without the effects of EB and a homogeneous problem that imposes the effects of EB. The inhomogeneous problem is efficiently solved through a geometric multi-grid (GMG) solver and the homogenous problem is solved through a boundary element method (BEM) utilizing the free space Green’s function. Our method is robust and can handle sharp geometric features without any special treatment. Analytical expressions are presented for the boundary and the domain integrals in BEM to reduce the computational cost and integration error relative to numerical quadratures. Furthermore, a fast multipole method (FMM) is employed to evaluate the boundary integrals in BEM and reduce the computational complexity of BEM. Our method inherits the complementary advantages of both GMG and FMM and presents an efficient alternative with linear computational complexity even for problems involving complex geometries. We observe that the overall computational cost is an order of magnitude lower compared with a stand-alone FMM and is similar to that of an ideal GMG solver.

MSC:

65N38 Boundary element methods for boundary value problems involving PDEs
65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
76M15 Boundary element methods applied to problems in fluid mechanics
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation

Software:

BEMLIB
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Askham, T.; Cerfon, A. J., An adaptive fast multipole accelerated Poisson solver for complex geometries, J. Comput. Phys., 344, 1-22 (2017) · Zbl 1380.65413
[2] Carrier, J.; Greengard, L.; Rokhlin, V., A fast adaptive multipole algorithm for particle simulations, SIAM J. Sci. Stat. Comput., 9, 669-686 (1988) · Zbl 0656.65004
[3] Cheng, H.; Greengard, L.; Rokhlin, V., A fast adaptive multipole algorithm in three dimensions, J. Comput. Phys., 155, 468-498 (1999) · Zbl 0937.65126
[4] Coco, A.; Russo, G., Finite-difference ghost-point multigrid methods on Cartesian grids for elliptic problems in arbitrary domains, J. Comput. Phys., 241, 464-501 (2013) · Zbl 1349.65555
[5] Coco, A.; Russo, G., Second order finite-difference ghost-point multigrid methods for elliptic problems with disconsitnuous coefficients on an arbitrary interface, J. Comput. Phys., 361, 299-330 (2018) · Zbl 1422.65306
[6] Crockett, R. K.; Colella, P.; Graves, D. T., A Cartesian grid embedded boundary method for solving the Poisson and heat equations with discontinuous coefficients in three dimensions, J. Comput. Phys., 230, 7, 2451-2469 (2011) · Zbl 1220.65121
[7] Devendran, D.; Graves, D. T.; Johansen, H.; Ligocki, T., A fourth-order Cartesian grid embedded boundary method for Poisson’s equation, Commun. Appl. Math. Comput. Sci., 12, 1, 51-79 (2017)
[8] Ethridge, F.; Greengard, L., A new fast-multipole accelerated Poisson solver in two dimensions, SIAM J. Sci. Comput., 23, 3, 741-760 (2001) · Zbl 1002.65131
[9] Gholami, A.; Malhotra, D.; Sundar, H.; Biros, G., 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, 3, C280-C306 (2016) · Zbl 1369.65138
[10] Guillet, T.; Teyssier, R., A simple multigrid scheme for solving the Poisson equation with arbitrary domain boundaries, J. Comput. Phys., 230, 4756-4771 (2011) · Zbl 1220.65171
[11] Gumerov, N. A.; Duraiswami, R., Fast Multipole Methods for the Helmholtz Equation in Three Dimensions, Elsevier Series in Electromagnetism. (2004), Elsevier Science: Elsevier Science Amsterdam
[12] Hosseinverdi, S.; Fasel, H. F., An efficient, high-order method for solving Poisson equation for immersed boundaries: combination of compact difference and multiscale multigrid methods, J. Comput. Phys., 374, 912-940 (2018) · Zbl 1416.65498
[13] Kavouklis, C.; Colella, P., Computation of volume potentials on structured grids via the method of local corrections, Commun. Appl. Math. Comput. Sci., 14, 1, 1-32 (2019)
[14] Langston, M. H.; Greengard, L.; Zorin, D., A free-space adaptive FMM-based PDE solver in three dimensions, Commun. Appl. Math. Comput. Sci., 6, 79-122 (2011) · Zbl 1230.65131
[15] Larsson, J.; Lien, F. S.; Yee, E., Conditional semicoarsening multigrid algorithm for the Poisson equation on anisotropic grids, J. Comput. Phys., 208, 368-383 (2005) · Zbl 1073.65116
[16] Liska, S.; Colonius, T., A parallel fast multipole method for elliptic difference equations, J. Comput. Phys., 278, 76-91 (2014) · Zbl 1349.65700
[17] Liska, S.; Colonius, T., A fast lattice Green’s function method for solving viscous incompressible flows on unbounded domains, J. Comput. Phys., 316, 360-384 (2016) · Zbl 1349.76501
[18] Liska, S.; Colonius, T., A fast immersed boundary method for external incompressible viscous flows using lattice green’s functions, J. Comput. Phys., 331, 257-279 (2017) · Zbl 1378.76083
[19] Liu, Y. J.; Nishimura, N., The fast multipole boundary element method for potential problems: a tutorial, Eng. Anal. Bound. Elem., 30, 5, 371-381 (2006) · Zbl 1187.65134
[20] Nishimura, N., Fast multipole accelerated boundary integral equation methods, Appl. Mech. Rev., 55, 299-324 (2002)
[21] Pozrikidis, C., A Practical Guide to Boundary Element Methods with the Software Library BEMLIB (2002), CRC Press, Inc.: CRC Press, Inc. Boca Raton, FL, USA · Zbl 1019.65097
[22] Pozrikidis, C., Numerical Computation in Science and Engineering (2008), Oxford University Press · Zbl 1152.65004
[23] Rapaka, N. R.; Samtaney, R., Non-normal stability of embedded boundary methods through pseudospectra, J. Comput. Phys., 373, 975-999 (2018) · Zbl 1416.76225
[24] Rapaka, N. R.; Sarkar, S., An immersed boundary method for direct and large eddy simulation of stratified flows in complex geometry, J. Comput. Phys., 322, 511-534 (2016) · Zbl 1351.76181
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.