A fast multi-level boundary element method for the Helmholtz equation. (English) Zbl 1075.76587

Summary: Most recently, we have developed a novel multi-level boundary element method (MLBEM) for the solution of the steady heat diffusion equation involving asymptotically decaying non-oscillatory log-singular and strongly singular kernels. This hierarchical approach generalizes the pioneering work of Brandt and Lubrecht on multi-level multi-integration (MLMI) and C-cycle multi-grid to the broader class of mixed boundary value problems. The result is a fast, accurate and efficient boundary element method. The present paper extends this new computational methodology to the solution of the Helmholtz equation involving oscillatory log-singular and strongly singular kernels for two-dimensional problems. We consider a direct boundary element formulation and, due to the nature of the fundamental solutions, split the corresponding boundary integral equation into real and imaginary parts. Then, we introduce double-noded corners to facilitate a patch-by-patch application of the MLMI algorithm for fast matrix–vector and matrix-transpose–vector multiplications within bi-conjugate gradient methods. The performance of the proposed fast MLBEM is investigated using a numerical example that possesses an exact solution. For wave numbers \(\kappa = 20\) and below, we demonstrate that the fast MLBEM algorithm for the Helmholtz equation is robust, accurate, and exceptionally efficient.


76M15 Boundary element methods applied to problems in fluid mechanics
76Q05 Hydro- and aero-acoustics
65N38 Boundary element methods for boundary value problems involving PDEs
Full Text: DOI


[1] Schenck, H. A., Improved integral formulation for acoustic radiation problems, J. Acoust. Soc. Am., 44, 41-58 (1968) · Zbl 0187.50302
[2] Meyer, W. L.; Bell, W. A.; Zinn, B. T.; Stallybrass, M. P., Boundary integral solutions of three dimensional acoustic radiation problems, J. Sound Vibration, 59, 245-262 (1978) · Zbl 0391.76052
[3] Bernhard, R. J.; Keltie, R. F., Numerical Techniques in Acoustic Radiation (1989), ASME: ASME New York
[4] Wu, T. W.; Li, W. L.; Seybert, A. F., An efficient boundary-element algorithm for multi-frequency acoustical analysis, J. Acoust. Soc. Am., 94, 447-452 (1993)
[5] Benthien, W.; Schenck, A., Nonexistence and nonuniqueness problems associated with integral equation methods in acoustics, Comput. & Structures, 65, 295-305 (1997) · Zbl 0918.76070
[6] Raveendra, S. T.; Vlahopoulos, N.; Glaves, A., An indirect formulation for multi-valued impedance simulation in structural acoustics, Appl. Math. Modelling, 22, 379-393 (1998) · Zbl 1428.76127
[7] Raveendra, S. T., An efficient indirect boundary element technique for multi-frequency acoustic analysis, Internat. J. Numer. Meth. Engrg., 44, 59-76 (1999) · Zbl 0924.76073
[8] Zhang, Z.; Vlahopoulos, N.; Raveendra, S. T.; Allen, T.; Zhang, K. Y., A computational acoustic field reconstruction process based on an indirect boundary element formulation, J. Acoust. Soc. Am., 108, 2167-2178 (2000)
[9] Gaul, L.; Wagner, M.; Wentzel, W.; Dumont, N., Numerical treatment of acoustic problems with the hybrid boundary element method, Internat. J. Solids Structures, 38, 1871-1888 (2001) · Zbl 1011.76055
[10] COMET/Acoustics: User’s Manual, Version 5.0, Collins & Aikman, Plymouth, MI, 2002; COMET/Acoustics: User’s Manual, Version 5.0, Collins & Aikman, Plymouth, MI, 2002
[11] Vavasis, A., Preconditioning for boundary integral equations, SIAM J. Matrix Anal. Appl., 13, 905-925 (1992) · Zbl 0755.65109
[12] Canning, F. X., Sparse approximation for solving integral equations with oscillatory kernels, SIAM J. Sci. Statist. Comput., 13, 71-87 (1992) · Zbl 0749.65093
[13] Atkinson, K. E.; Graham, I. G., Iterative solution of linear equations arising from the boundary integral method, SIAM J. Sci. Statist. Comput., 13, 694-722 (1992) · Zbl 0809.65110
[14] Chen, K.; Amini, S., Numerical analysis of boundary integral solution of the Helmholtz equation in domains with non-smooth boundaries, IMA J. Numer. Anal., 13, 43-66 (1993) · Zbl 0762.65063
[15] Amini, S.; Maines, N. D., Preconditioned Krylov subspace methods for boundary element solution of the Helmholtz equation, Internat. J. Numer. Meth. Engrg., 41, 875-898 (1998) · Zbl 0907.65118
[16] Chen, K.; Harris, P. J., Efficient preconditioners for iterative solution of the boundary element equations for the three-dimensional Helmholtz equation, Appl. Numer. Math., 36, 475-489 (2001) · Zbl 0979.65107
[17] Brandt, A., Multi-level adaptive solutions to boundary-value problems, Math. Comput., 31, 333-390 (1977) · Zbl 0373.65054
[18] Brandt, A., Multilevel computations: review and recent developments, (Multigrid Methods (Copper Mountain, CO, 1987). Multigrid Methods (Copper Mountain, CO, 1987), Lecture Notes in Pure and Applied Mathematics, vol. 110 (1988), Dekker: Dekker New York), 35-62 · Zbl 0652.65074
[19] (Hackbush, W.; Trottenberg, U., Multigrid Methods II. Proceedings of the Second European Conference. Multigrid Methods II. Proceedings of the Second European Conference, Lecture Notes in Mathematics, vol. 1228 (1986), Springer-Verlag: Springer-Verlag Berlin)
[20] Barnes, J.; Hut, P., A hierarchical \(O(n\)·log \(n)\) force calculation algorithm, Nature, 324, 446-449 (1986)
[21] Grama, A.; Kumar, A.; Sameh, A., Parallel hierarchical solvers and preconditioners for boundary element methods, SIAM J. Sci. Comput., 20, 337-358 (1998) · Zbl 0919.65068
[22] Beylkin, G.; Coifman, R.; Rokhlin, V., Fast wavelet transforms and numerical algorithms. 1, Commun. Pure Appl. Math., 44, 141-183 (1991) · Zbl 0722.65022
[23] Alpert, B., A class of bases in \(L^2\) for the sparse representation of integral operators, SIAM J. Math. Anal., 24, 246-262 (1993) · Zbl 0764.42017
[24] Alpert, B.; Beylkin, G.; Coifman, R.; Rokhlin, V., Waveletlike bases for the fast solution of second-kind integral equations, SIAM J. Sci. Comput., 14, 159-184 (1993) · Zbl 0771.65088
[25] von Petersdorff, T.; Schwab, C.; Schneider, R., Multiwavelets for second-kind integral equations, SIAM J. Numer. Anal., 34, 2212-2227 (1997) · Zbl 0891.65121
[26] Rokhlin, V., Rapid solution of integral equations of classical potential theory, J. Comput. Phys., 60, 187-207 (1985) · Zbl 0629.65122
[27] Greengard, L.; Rokhlin, V., A fast algorithm for particle simulations, J. Comput. Phys., 73, 325-348 (1987) · Zbl 0629.65005
[28] Rokhlin, V., Rapid solutions of integral equations of scattering theory in two dimensions, J. Comput. Phys., 86, 414-439 (1990) · Zbl 0686.65079
[29] Coifman, R.; Rokhlin, V.; Wandzura, S., The fast multipole method for the wave equation: a pedestrian prescription, IEEE Trans. Antennas and Propagation, 35, 7-12 (1993)
[30] Lu, C. C.; Chew, W. C., A multilevel algorithm for solving a boundary integral equation of wave scattering, Microwave Opt. Tech. Lett., 7, 466-470 (1994)
[31] Nabors, K.; Korsmeyer, F. T.; Leighton, F. T.; White, J., Preconditioned, adaptive, multipole-accelerated iterative methods for three-dimensional first-kind integral equations of potential theory, SIAM J. Sci. Comput., 15, 713-735 (1994) · Zbl 0801.65131
[32] Petersen, H. G.; Smith, E. R.; Soelvason, D., Error-estimates for the fast multipole method. 2. The 3-dimensional case, Proc. Roy. Soc. London A, 448, 401-418 (1995) · Zbl 0831.65136
[33] Epton, M. A.; Dembart, B., Multipole translation theory for the three-dimensional Laplace and Helmholtz equations, SIAM J. Sci. Comput., 16, 865-897 (1995) · Zbl 0852.31006
[34] Rahola, J., Diagonal forms of the translation operators in the fast multipole algorithm for scattering problems, BIT, 36, 333-358 (1996) · Zbl 0854.65122
[35] Greengard, L.; Lee, J. Y., A direct adaptive Poisson solver of arbitrary order accuracy, J. Comput. Phys., 125, 415-424 (1996) · Zbl 0851.65090
[36] Cheng, H.; Greengard, L.; Rokhlin, V., A fast adaptive multipole algorithm in three dimensions, J. Comput. Phys., 155, 468-498 (1999) · Zbl 0937.65126
[37] Pham, H. H.; Nathan, A., A new approach for rapid evaluation of the potential field in three dimensions, Proc. Roy. Soc. London A, 455, 637-675 (1999) · Zbl 0927.35027
[38] Koc, S.; Song, J.; Chew, W. C., Error analysis for the numerical evaluation of the diagonal forms of the scalar spherical addition theorem, SIAM J. Numer. Anal., 36, 906-921 (1999) · Zbl 0924.65116
[39] Darve, E., The fast multipole method: numerical implementation, J. Comput. Phys., 160, 195-240 (2000) · Zbl 0974.78012
[40] Darve, E., The fast multipole method 1: error analysis and asymptotic complexity, SIAM J. Numer. Anal., 38, 98-128 (2000) · Zbl 0974.65033
[41] Gumerov, N. A.; Duraiswami, R., Computation of scattering from \(N\) spheres using multipole reexpansion, J. Acoust. Soc. Am., 112, 2688-2701 (2002)
[42] Amini, S.; Profit, A. T.J., Multi-level fast multipole solution of the scattering problem, Engrg. Anal. Bound. Elem., 27, 547-564 (2003) · Zbl 1039.65084
[43] Hastriter, M. L.; Ohnuki, S.; Chew, W. C., Error control of the translation operator in 3D MLFMA, Microwave Opt. Techn. Lett., 37, 184-188 (2003)
[44] Brandt, A.; Lubrecht, A. A., Multilevel matrix multiplication and fast solution of integral equations, J. Comput. Phys., 90, 348-370 (1990) · Zbl 0707.65025
[45] Lubrecht, A.; Ioannides, E., A fast solution of the dry contact problem and the associated subsurface stress field using mutlilevel techniques, ASME J. Tribol., 113, 128-133 (1991)
[46] Polonsky, I. A.; Keer, L. M., A numerical method for solving rough contact problems based on the multi-level multi-summation and conjugate gradient techniques, Wear, 231, 206-219 (1999)
[47] Polonsky, I. A.; Keer, L. M., Fast methods for solving rough contact problems: a comparative study, ASME J. Tribol., 122, 36-41 (2000)
[48] Venner, C. H.; Lubrecht, A. A., Multi-level Methods in Lubrication (2000), Elsevier: Elsevier Amsterdam · Zbl 0815.65087
[49] Brandt, A., Multilevel computations of integral transforms and particle interactions with oscillatory kernels, Comput. Phys. Commun., 65, 24-38 (1991) · Zbl 0900.65121
[50] M.M. Grigoriev, G.F. Dargush, A fast multi-level boundary element method for the Laplace equation, Internat. J. Numer. Meth. Engrg., submitted for publication; M.M. Grigoriev, G.F. Dargush, A fast multi-level boundary element method for the Laplace equation, Internat. J. Numer. Meth. Engrg., submitted for publication · Zbl 1075.76587
[51] Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P., Numerical Recipes in C. The Art of Scientific Computing (1992), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0845.65001
[52] Banerjee, P. K., The Boundary Element Methods in Engineering (1994), McGraw-Hill: McGraw-Hill London
[53] Hemker, P. W.; Schippers, H., Multiple grid methods for the solution of Fredholm integral equations of the second kind, Math. Comput., 36, 215-232 (1981) · Zbl 0463.65086
[54] Schippers, H., Multiple grid methods for boundary integral-equations, Numer. Math., 46, 351-363 (1985) · Zbl 0543.65015
[55] von Petersdorff, T.; Stephan, E. P., On the convergence of the multigrid method for a hypersingular integral equation of the first kind, Numer. Math., 57, 379-391 (1990) · Zbl 0702.65102
[56] F.K. Hebeker, On multigrid methods of the first kind for symmetric boundary integral equations of nonnegative order, TH-Darmstadt, Preprint 1120, 1988; F.K. Hebeker, On multigrid methods of the first kind for symmetric boundary integral equations of nonnegative order, TH-Darmstadt, Preprint 1120, 1988
[57] Atkinson, K. E., Two-grid iteration methods for linear integral-equations of the 2nd kind on piecewise-smooth surface in \(R^3\), SIAM J. Sci. Comput., 15, 1083-1104 (1994) · Zbl 0810.65113
[58] Greenberg, M. D., Advanced Engineering Mathematics (1998), Prentice-Hall: Prentice-Hall Upper Saddle River, NJ · Zbl 0893.00006
[59] Prudnikov, A. P.; Brychkov, Yu. A.; Marichev, O. I., Integrals and Series. Volume 2: Special Functions (1986), Gordon and Breach Science Publishers: Gordon and Breach Science Publishers New York · Zbl 0733.00004
[60] Abramowitz, M.; Stegun, I. A., Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables (1964), Dover: Dover New York · Zbl 0171.38503
[61] Grigoriev, M. M.; Dargush, G. F., Boundary element methods for transient convective diffusion. Part II: 2d implementation, Comput. Methods Appl. Mech. Engrg., 192, 4313-4335 (2003) · Zbl 1054.76058
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.