An efficient \(\mathcal O(N)\) algorithm for computing \(\mathcal O(N^2)\) acoustic wave interactions in large \(N\)-obstacle three dimensional configurations. (English) Zbl 1311.65156

Summary: We develop and implement a fast and memory efficient scheme for simulating the wave interactions between large numbers of particles. This is crucial for iteratively computing a time harmonic acoustic field exterior to a configuration of the particles. The main focus of this article is on efficient computation of the wave interactions between the particles in any iterative multiple scattering approach. We develop our algorithm in four stages and demonstrate the efficiency of our interaction evaluation algorithm at each stage for configurations with several thousand convex and non-convex particles. Using this efficient approach, we simulate the full large particle wave propagation models using a flexible generalized minimal residual (GMRES) based inner-outer preconditioned multiple scattering iterative technique on a single compute node.


65N38 Boundary element methods for boundary value problems involving PDEs
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
65F08 Preconditioners for iterative methods
76M15 Boundary element methods applied to problems in fluid mechanics
76Q05 Hydro- and aero-acoustics


Full Text: DOI


[1] Anand, A; Boubendir, Y; Ecevit, F; Reitich, F, Analysis of multiple scattering iterations for high-frequency scattering problems. ii: the three-dimensional scalar case, Numer. Math., 114, 373-427, (2010) · Zbl 1196.65180
[2] Balabane, M.: Boundary decomposition for Helmholtz and Maxwell equations 1: disjoint sub-scatterers. Asymp. Anal. 38, 1-10 (2004) · Zbl 1099.35023
[3] Cheng, H., et al.: A wideband fast multipole method for the Helmholtz equation in three dimensions. J. Comput. Phys. 216, 300-325 (2006) · Zbl 1093.65117
[4] Chew, W.C., Jin, J., Michielssen, E., Song, J.: Fast and Efficient Algorithms in Computational Electromagnetics. Artech House, London (2001) · Zbl 1052.65108
[5] Colton, D., Kress, R.: Inverse Acoustic and Electromagnetic Scattering Theory. Springer, Berlin (2012) · Zbl 0893.35138
[6] Dufva, TJ; Sarvas, J; Sten, JCE, Unified derivation of the translation addition theorems for the spherical and vector wave functions, Progr. Electromagnet. Res. B, 4, 79-99, (2008)
[7] Ganesh, M; Graham, IG, A high-order algorithm for obstacle scattering in three dimensions, J. Comput. Phys., 198, 211-242, (2004) · Zbl 1052.65108
[8] Ganesh, M; Hawkins, SC, A high-order algorithm for multiple electromagnetic scattering in three dimensions, Numer. Algorithms, 50, 469-510, (2009) · Zbl 1175.78011
[9] Ganesh, M., Hawkins, S.C.: Iterative algorithms for multiple electromagnetic scattering in three dimensions. In: International Conference on Days of Diffraction, pp. 63-68 (2010) · Zbl 1175.78011
[10] Ganesh, M., Hawkins, S.C.: A stochastic pseudospectral and T-matrix algorithm for acoustic scattering by a class of multiple particle configurations. J. Quant. Spect. Radiat. Transf. 123, 41-52 (2013)
[11] Ganesh, M., Hawkins, S.C., Hiptmair, R.: Convergence analysis with parameter estimates for a reduced basis acoustic scattering T-matrix method. IMA J. Numer. Anal. 32, 1348-1374 (2012) · Zbl 1275.65074
[12] Ganesh, M; Hesthaven, J; Stamm, B, A reduced basis method for multiple electromagnetic scattering in three dimensions, J. Comput. Phys., 231, 7756-7779, (2012) · Zbl 1254.78012
[13] Graham, I.G., Spence, E., Chandler-Wilde, S., Langdon, S.: Numerical-asymptotic boundary integral methods in high-frequency scattering. ACTA Numerica 21, 89-305 (2012) · Zbl 1257.65070
[14] Hellmers, J., Eremina, E., Wriedt, T.: Simulation of light scattering by biconcave Cassini ovals using the nullfield method with discrete sources. J. Opt. A: Pure Appl. Opt.8, 1-9 (2006)
[15] Hiptmair, R., Kielhorn, L.: BETL—a generic boundary element template library. Tech. Rep. 2012-36, Seminar for Applied Mathematics, ETH Zürich. (http://www.sam.math.ethz.ch/betl/) (2012)
[16] Martin, P.A.: Multiple Scattering: Interaction of Time-Harmonic Waves with N Obstacles. Cambridge University Press, Oxford (2006) · Zbl 1210.35002
[17] Mishchenko, M.I., Travis, L.D., Lacis, A.A.: Multiple Scattering of Light by Particles: Radiative Transfer and Coherent Backscattering. Cambridge University Press, Oxford (2006)
[18] Mishchenko, MI; Travis, LD; Mackowski, DW, T-matrix computations of light scattering by nonspherical particles: a review, J. Quant. Spectrosc. Radiat. Transf., 55, 535-575, (1996)
[19] Monk, P.: Finite Element Methods for Maxwell’s Equations. Oxford University Press, Oxford (2003) · Zbl 1024.78009
[20] Nédélec, J.C.: Acoustic and Electromagnetic Equations. Springer, Berlin (2001) · Zbl 0981.35002
[21] Saad, Y.: A flexible inner-outer preconditioned GMRES algorithm. SIAM J. Sci. Comput. 14(2), 461-469 (1993) · Zbl 0780.65022
[22] Śmigaj, W., Arridge, S., Betcke, T., Phillips, J., Schweiger, M.: Solving boundary integral problems with BEM++. ACM Trans. Math. Softw. (to appear, 2014). http://www.bempp.org/files/bempp-toms-preprint.pdf · Zbl 1371.65127
[23] Song, J; Lu, CC; Chew, WC, Multilevel fast multipole algorithm for electromagnetic scattering by large complex objects, IEEE Trans. Antennas Propag., 45, 1488-1493, (1997)
[24] Wriedt, T; Hellmers, J; Eremina, E; Schuh, R, Light scattering by single erythrocyte: comparison of different methods, J. Quant. Spectrosc. Radiat. Transf., 100, 444-456, (2006)
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.