A fourth-order kernel-free boundary integral method for the modified Helmholtz equation. (English) Zbl 1418.35094

J. Sci. Comput. 78, No. 3, 1632-1658 (2019); correction ibid. 78, No. 3, 1659 (2019).
Summary: Based on the kernel-free boundary integral method proposed by W. Ying and C. S. Henriquez [J. Comput. Phys. 227, No. 2, 1046–1074 (2007; Zbl 1128.65102)], which is a second-order accurate method for general elliptic partial differential equations, this work develops it to be a fourth-order accurate version for the modified Helmholtz equation. The updated method is in line with the original one. Unlike the traditional boundary integral method, it does not need to know any analytical expression of the fundamental solution or Green’s function in evaluation of boundary or volume integrals. Boundary value problems under consideration are reformulated into Fredholm boundary integral equations of the second kind, whose corresponding discrete forms are solved with the simplest Krylov subspace iterative method, the Richardson iteration. During each iteration, a Cartesian grid based nine-point compact difference scheme is used to discretize the simple interface problem whose solution is the boundary or volume integral in the BIEs. The resulting linear system is solved by a fast Fourier transform based solver, whose computational work is roughly proportional to the number of grid nodes in the Cartesian grid used. As the discrete boundary integral equations are well-conditioned, the iteration converges within an essentially fixed number of steps, independent of the mesh parameter. Numerical results are presented to verify the solution accuracy and demonstrate the algorithm efficiency.


35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
35J25 Boundary value problems for second-order elliptic equations
65N38 Boundary element methods for boundary value problems involving PDEs
65N06 Finite difference methods for boundary value problems involving PDEs
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs


Zbl 1128.65102


Full Text: DOI


[1] Atkinson, K.E.: The Numerical Solution of Integral Equations of the Second Kind. Cambridge University Press, Cambridge (1997) · Zbl 0899.65077
[2] Ben Avraham, D.; Fokas, AS, The solution of the modified Helmholtz equation in a wedge and an application to diffusion-limited coalescence, Phys. Lett. A, 263, 355-359, (1999) · Zbl 0947.35040
[3] Bakker, M., Modeling groundwater flow to elliptical lakes and through multi-aquifer elliptical inhomogeneities, Adv. Water Resour., 27, 497-506, (2004)
[4] Bakker, M.; Kuhlman, KL, Computational issues and applications of line-elements to model subsurface flow governed by the modified Helmholtz equation, Adv. Water Resour., 34, 1186-1194, (2011)
[5] Banerjee, P.K., Butterfield, R.: Boundary Element Methods in Engineering Science, vol. 17. McGraw-Hill, London (1981) · Zbl 0499.73070
[6] Barnes, J.; Hut, P., A hierarchical O(N log N) force-calculation algorithm, Nature, 324, 446, (1986)
[7] Barnes, JE, A modified tree code: Don’t laugh. It runs., J. Comput. Phys., 87, 161-170, (1990) · Zbl 0689.68002
[8] Bazant, MZ; Thornton, K.; Ajdari, A., Diffuse-charge dynamics in electrochemical systems, Phys. Rev. E, 70, 021506, (2004)
[9] Beale, JT; Layton, AT, On the accuracy of finite difference methods for elliptic problems with interfaces, Commun. Appl. Math. Comput. Sci., 1, 91-119, (2006) · Zbl 1153.35319
[10] Brebbia, C.; Dominguez, J., Boundary element methods for potential problems, Appl. Math. Model., 1, 372-378, (1977) · Zbl 0373.31007
[11] Chapko, R.; Kress, R., Rothe’s method for the heat equation and boundary integral equations, J. Integral Equ. Appl., 9, 47-69, (1997) · Zbl 0885.65101
[12] Cheng, H.; Crutchfield, WY; Gimbutas, Z.; Greengard, LF; Ethridge, JF; Huang, J.; Rokhlin, V.; Yarvin, N.; Zhao, J., A wideband fast multipole method for the Helmholtz equation in three dimensions, J. Comput. Phys., 216, 300-325, (2006) · Zbl 1093.65117
[13] Cheng, H.; Greengard, L.; Rokhlin, V., A fast adaptive multipole algorithm in three dimensions, J. Comput. Phys., 155, 468-498, (1999) · Zbl 0937.65126
[14] Cheng, H.; Huang, J.; Leiterman, TJ, An adaptive fast solver for the modified Helmholtz equation in two dimensions, J. Comput. Phys., 211, 616-637, (2006) · Zbl 1117.65161
[15] Di Gioia, A.: Fast multipole accelerated boundary element techniques for large-scale problems, with applications to MEMS. Ph.D. thesis, Università di Trento. Dipartimento di ingegneria meccanica e strutturale (2005)
[16] Fedkiw, RP; Aslam, T.; Merriman, B.; Osher, S., A non-oscillatory eulerian approach to interfaces in multimaterial flows (the ghost fluid method), J. Comput. Phys., 152, 457-492, (1999) · Zbl 0957.76052
[17] Feng, H.; Barua, A.; Li, S.; Li, X., A parallel adaptive treecode algorithm for evolution of elastically stressed solids, Commun. Comput. Phys., 15, 365-387, (2014) · Zbl 1373.74012
[18] Gibou, F.; Fedkiw, R.; Cheng, LT; Kang, M., A second order accurate symmetric discretization of the Poisson equation on irregular domains, J. Comput. Phys., 176, 205-227, (2002) · Zbl 0996.65108
[19] Gibou, F.; Fedkiw, RP, A fourth order accurate discretization for the Laplace and heat equations on arbitrary domains, with applications to the Stefan problem, J. Comput. Phys., 202, 577-601, (2005) · Zbl 1061.65079
[20] Greengard, L.; Huang, J.; Rokhlin, V.; Wandzura, S., Accelerating fast multipole methods for the Helmholtz equation at low frequencies, IEEE Comput. Sci. Eng., 5, 32-38, (1998)
[21] Greengard, L.; Kropinski, MC, An integral equation approach to the incompressible Navier-Stokes equations in two dimensions, SIAM J. Sci. Comput., 20, 318-336, (1998) · Zbl 0917.35094
[22] Greengard, L.; Rokhlin, V., A fast algorithm for particle simulations, J. Comput. Phys., 73, 325-348, (1987) · Zbl 0629.65005
[23] Greengard, L.; Rokhlin, V., A new version of the fast multipole method for the Laplace equation in three dimensions, Acta Numer., 6, 229-269, (1997) · Zbl 0889.65115
[24] Hackbusch, W.: Integral Equations, Theory and Numerical Treatment. Birkhäuser, Basel (1995) · Zbl 0823.65139
[25] Hackbusch, W.; Nowak, ZP, On the fast matrix multiplication in the boundary element method by panel clustering, Numer. Math., 54, 463-491, (1989) · Zbl 0641.65038
[26] He, X.; Lin, T.; Lin, Y., Immersed finite element methods for elliptic interface problems with non-homogeneous jump conditions, Int. J. Numer. Anal. Model., 8, 284-301, (2011) · Zbl 1211.65155
[27] Hewett, DW, The embedded curved boundary method for orthogonal simulation meshes, J. Comput. Phys., 138, 585-616, (1997) · Zbl 0897.65069
[28] Hou, S.; Liu, XD, A numerical method for solving variable coefficient elliptic equation with interfaces, J. Comput. Phys., 202, 411-445, (2005) · Zbl 1061.65123
[29] Houstis, EN; Papatheodorou, TS, Algorithm 543: FFT9, fast solution of Helmholtz-type partial differential equations D3, ACM Trans. Math. Softw., 5, 490-493, (1979) · Zbl 0432.65055
[30] Houstis, EN; Papatheodorou, TS, High-order fast elliptic equation solver, ACM Trans. Math. Softw., 5, 431-441, (1979) · Zbl 0432.65054
[31] Hsiao, G.C., Wendland, W.L.: Boundary Integral Equations. Springer, Berlin (2008) · Zbl 1157.65066
[32] Jaswon, M.: Integral equation methods in potential theory. I. In: Proceedings of the Royal Society of London A, vol. 275, pp. 23-32. The Royal Society (1963) · Zbl 0112.33103
[33] Johansen, H.; Colella, P., A Cartesian grid embedded boundary method for Poisson’s equation on irregular domains, J. Comput. Phys., 147, 60-85, (1998) · Zbl 0923.65079
[34] Kropinski, MCA; Quaife, BD, Fast integral equation methods for Rothe’s method applied to the isotropic heat equation, Comput. Math. Appl., 61, 2436-2446, (2011) · Zbl 1221.65279
[35] Kropinski, MCA; Quaife, BD, Fast integral equation methods for the modified Helmholtz equation, J. Comput. Phys., 230, 425-434, (2011) · Zbl 1207.65144
[36] Kuhlman, KL; Neuman, SP, Laplace-transform analytic-element method for transient porous-media flow, J. Eng. Math., 64, 113, (2009) · Zbl 1168.76369
[37] Le, DV; Khoo, BC; Peraire, J., An immersed interface method for viscous incompressible flows involving rigid and flexible boundaries, J. Comput. Phys., 220, 109-138, (2006) · Zbl 1158.74349
[38] Leveque, RJ; Li, Z., The immersed interface method for elliptic equations with discontinuous coefficients and singular sources, SIAM J. Numer. Anal., 31, 1019-1044, (1994) · Zbl 0811.65083
[39] Li, H., Huang, J.: High accuracy solutions of the modified Helmholtz equation. In: Information Technology and Intelligent Transportation Systems, pp. 29-37. Springer (2017)
[40] Li, Z., A fast iterative algorithm for elliptic interface problems, SIAM J. Numer. Anal., 35, 230-254, (1998) · Zbl 0915.65121
[41] Li, Z., Ito, K.: The Immersed Interface Method: Numerical Solutions of PDEs Involving Interfaces and Irregular Domains, vol. 33. SIAM, Philadelphia (2006) · Zbl 1122.65096
[42] Lindsay, K.; Krasny, RA, A particle method and adaptive treecode for vortex sheet motion in three-dimensional flow, J. Comput. Phys., 172, 879-907, (2001) · Zbl 1002.76093
[43] Liu, Y.; Nishimura, N., The fast multipole boundary element method for potential problems: a tutorial, Eng. Anal. Bound. Elem., 30, 371-381, (2006) · Zbl 1187.65134
[44] Marques, AN; Nave, JC; Rosales, RR, A correction function method for Poisson problems with interface jump conditions, J. Comput. Phys., 230, 7567-7597, (2011) · Zbl 1453.35054
[45] Marques, AN; Nave, JC; Rosales, RR, High order solution of Poisson problems with piecewise constant coefficients and interface jumps, J. Comput. Phys., 335, 497-515, (2017) · Zbl 1380.65224
[46] Mayo, A., The fast solution of Poisson’s and the biharmonic equations on irregular regions, SIAM J. Numer. Anal., 21, 285-299, (1984) · Zbl 1131.65303
[47] Mayo, A., Fast high order accurate solution of Laplace’s equation on irregular regions, SIAM J. Sci. Stat. Comput., 6, 144-157, (1985) · Zbl 0559.65082
[48] Mayo, A., The rapid evaluation of volume integrals of potential theory on general regions, J. Comput. Phys., 100, 236-245, (1992) · Zbl 0772.65012
[49] Peskin, CS, The immersed boundary method, Acta Numer., 11, 479-517, (2002) · Zbl 1123.74309
[50] Phillips, JR; White, JK, A precorrected-FFT method for electrostatic analysis of complicated 3-D structures, IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 16, 1059-1072, (1997)
[51] Politis, CG; Papalexandris, MV; Athanassoulis, GA, A boundary integral equation method for oblique water-wave scattering by cylinders governed by the modified helmholtz equation, Appl. Ocean Res., 24, 215-233, (2002)
[52] Quaife, B.D.: Fast integral equation methods for the modified Helmholtz equation. Ph.D. thesis, Science: Department of Mathematics (2011) · Zbl 1207.65144
[53] Rokhlin, V., Rapid solution of integral equations of classical potential theory, J. Comput. Phys., 60, 187-207, (1985) · Zbl 0629.65122
[54] Rosser, JB, Nine-point difference solutions for Poisson’s equation, Comput. Math. Appl., 1, 351-360, (1975) · Zbl 0334.65079
[55] Saad, Y.; Schultz, MH, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7, 856-869, (1986) · Zbl 0599.65018
[56] Samarskii, A.A.: The Theory of Difference Schemes, vol. 240. CRC Press, London (2001) · Zbl 0971.65076
[57] Sauter, S., Schwab, C.: Boundary Element Methods. Springer, Berlin (2010) · Zbl 1215.65183
[58] Steinbach, O.: Numerical Approximation Methods for Elliptic Boundary Value Problems: Finite and Boundary Elements. Springer, Berlin (2007)
[59] Strack, O.D.: Groundwater Mechanics. Prentice Hall, Englewood Cliffs (1989)
[60] Ying, L.; Biros, G.; Zorin, D., A kernel-independent adaptive fast multipole algorithm in two and three space dimensions, J. Comput. Phys., 196, 591-626, (2004) · Zbl 1053.65095
[61] Ying, L.; Biros, G.; Zorin, D., A high-order 3D boundary integral equation solver for elliptic PDEs in smooth domains, J. Comput. Phys., 219, 247-275, (2006) · Zbl 1105.65115
[62] Ying, W.; Henriquez, CS, A kernel-free boundary integral method for elliptic boundary value problems, J. Comput. Phys., 227, 1046-1074, (2007) · Zbl 1128.65102
[63] Ying, W.; Wang, WC, A kernel-free boundary integral method for implicitly defined surfaces, J. Comput. Phys., 252, 606-624, (2013) · Zbl 1349.65662
[64] Ying, W.; Wang, WC, A kernel-free boundary integral method for variable coefficients elliptic PDEs., Commun. Comput. Phys., 15, 1108-1140, (2014) · Zbl 1388.65171
[65] Zhou, YC; Zhao, S.; Feig, M.; Wei, GW, High order matched interface and boundary method for elliptic equations with discontinuous coefficients and singular sources, J. Comput. Phys., 213, 1-30, (2006) · Zbl 1089.65117
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.