×

Distributed fast boundary element methods for Helmholtz problems. (English) Zbl 1433.65325

Summary: We present an approach for a distributed memory parallelization of the boundary element method. The given mesh is decomposed into submeshes and the respective matrix blocks are distributed among computational nodes (processes). The distribution which takes care of the load balancing during the system matrix assembly and matrix-vector multiplication is based on the cyclic graph decomposition. Moreover, since the individual matrix blocks are approximated using the adaptive cross approximation method, we describe its modification capable of dealing with zero blocks in the double-layer operator matrix since these are usually problematic when using the original adaptive cross approximation algorithm. Convergence and scalability of the method are demonstrated on the half- and full-space sound scattering problems modeled by the Helmholtz equation.

MSC:

65N38 Boundary element methods for boundary value problems involving PDEs
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
35J25 Boundary value problems for second-order elliptic equations

Software:

BEM4I
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Rjasanow, S.; Steinbach, O., The Fast Solution of Boundary Integral Equations (2007), Springer · Zbl 1119.65119
[2] Steinbach, O., Numerical Approximation Methods for Elliptic Boundary Value Problems: Finite and Boundary Elements, Texts in applied mathematics (2008), Springer · Zbl 1153.65302
[3] Sauter, S.; Schwab, C., Boundary Element Methods, Springer Series in Computational Mathematics (2010), Springer
[4] Bebendorf, M., Approximation of boundary element matrices, Numer. Math., 86 (2000) · Zbl 0966.65094
[5] Bebendorf, M., Hierarchical Matrices (2008), Springer · Zbl 1151.65090
[6] Hackbusch, W.; Nowak, Z., On the fast matrix multiplication in the boundary element methods by panel clustering, Numer. Math., 54 (1989) · Zbl 0641.65038
[7] Rokhlin, V., Rapid solution of integral equations of classical potential theory, Journal of Computational Physics, 60, 2, 187-207 (1985) · Zbl 0629.65122
[8] Greengard, L.; Rokhlin, V., A fast algorithm for particle simulations, Journal of Computational Physics, 135, 2, 280-292 (1997) · Zbl 0898.70002
[9] Of, G., Fast multipole methods and applications, (Schanz, M.; Steinbach, O., Boundary Element Analysis. Boundary Element Analysis, Lecture Notes in Applied and Computational Mechanics, 29 (2007), Springer Berlin Heidelberg), 135-160 · Zbl 1298.74245
[10] Gumerov, N. A.; Duraiswami, R., A broadband fast multipole accelerated boundary element method for the three dimensional helmholtz equation, The Journal of the Acoustical Society of America, 125, 1, 191-205 (2009)
[11] Dahmen, W.; Harbrecht, H.; Schneider, R., Compression techniques for boundary integral equations—asymptotically optimal complexity estimates, SIAM Journal on Numerical Analysis, 43, 6, 2251-2271 (2006) · Zbl 1113.65114
[12] Dahlke, S.; Harbrecht, H.; Utzinger, M.; Weimar, M., Adaptive wavelet bem for boundary integral equations: Theory and numerical experiments, Numerical Functional Analysis and Optimization, 39, 2, 208-232 (2018) · Zbl 1388.31008
[13] Bebendorf, M.; Rjasanow, S., Adaptive low-rank approximation of collocation matrices, Computing, 70, 1, 1-24 (2003) · Zbl 1068.41052
[14] Zapletal, J.; Of, G.; Merta, M., Parallel and vectorized implementation of analytic evaluation of boundary integral operators, Engineering Analysis with Boundary Elements, 96, 194-208 (2018) · Zbl 1403.65240
[15] Zapletal, J.; Merta, M.; Maly, L., Boundary element quadrature schemes for multi- and many-core architectures, Computers and Mathematics with Applications, 74, 1, 157-173 (2017) · Zbl 1375.65164
[16] Vater, K.; Betcke, T.; Dilba, B., Simple and efficient GPU parallelization of existing H-matrix accelerated BEM code, CoRR, abs/1711.01897 (2017)
[17] Zaspel, P., Algorithmic patterns for H-matrices on many-core processors, Journal of Scientific Computing (2018) · Zbl 1434.65062
[18] Börm, S.; Christophersen, S., Approximation of BEM matrices using GPGPUs, CoRR, abs/1510.07244 (2015)
[19] Lukáš, D.; Kovář, P.; Kovářová, T.; Merta, M., A parallel fast boundary element method using cyclic graph decompositions, Numerical Algorithms, 70, 4, 807-824 (2015) · Zbl 1332.65177
[20] Bebendorf, M.; Kriemann, R., Fast parallel solution of boundary integral equations and related problems, Computing and Visualization in Science, 8, 3-4, 121-135 (2005) · Zbl 1512.65299
[21] Bapat, M.; Shen, L.; Liu, Y., Adaptive fast multipole boundary element method for three-dimensional half-space acoustic wave problems, Engineering Analysis with Boundary Elements, 33, 8-9, 1113-1123 (2009) · Zbl 1244.76030
[22] Wang, X.; Zhang, J.; Zheng, X.; Zhou, F., Half space acoustic problems analysis by fast multipole boundary face method, Computer Modeling in Engineering and Sciences, 93, 1, 69-90 (2013) · Zbl 1356.74246
[23] Brunner, D.; Junge, M.; Rapp, P.; Bebendorf, M.; Gaul, L., Comparison of the fast multipole method with hierarchical matrices for the Helmholtz-BEM, Computer Modeling in Engineering and Sciences, 58, 2, 131-158 (2010) · Zbl 1231.74454
[24] Seybert, A.; Wu, T., Modified Helmholtz integral equation for bodies sitting on an infinite plane, Journal of the Acoustical Society of America, 85, 1, 19-23 (1989)
[25] Zapletal, J.; Bouchala, J., Effective semi-analytic integration for hypersingular Galerkin boundary integral equations for the Helmholtz equation in 3D, Applications of Mathematics, 59, 5, 527-542 (2014) · Zbl 1340.65282
[26] Burton, A. J.; Miller, G. F., The application of integral equation methods to the numerical solution of some exterior boundary-value problems, Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 323, 201-210 (1971) · Zbl 0235.65080
[27] Bebendorf, M.; Kriemann, R., Fast parallel solution of boundary integral equations and related problems, Comp. Vis. Sci., 8 (2005) · Zbl 1512.65299
[28] Börm, S.; Grasedyck, L., Hybrid cross approximation of integral operators, Numerische Mathematik, 101, 2, 221-249 (2005) · Zbl 1104.65120
[29] Grasedyck, L., Adaptive recompression of H-Matrices for BEM, Computing, 74, 3, 205-223 (2005) · Zbl 1070.65028
[30] M. Merta, J. Zapletal, BEM4I, IT4Innovations, VŠB - Technical University of Ostrava, 17. listopadu 2172/15, 708 00 Ostrava-Poruba, Czech Republic, 2013.
[31] Karypis, G.; Kumar, V., A fast and high quality multilevel scheme for partitioning irregular graphs, SIAM Journal on Scientific Computing, 20, 1, 359-392 (1999) · Zbl 0915.68129
[32] Singer, J., A theorem of finite projective geometry and some applications to number theory, Trans. Amer. Math. Soc., 43, 4, 377-385 (1938) · JFM 64.0972.04
[33] Ghysels, P.; Ashby, T.; Meerbergen, K.; Vanroose, W., Hiding global communication latency in the gmres algorithm on massively parallel machines, SIAM J. Sci. Comput., 35, 1, C48-C71 (2013) · Zbl 1273.65050
[34] Ghysels, P.; Vanroose, W., Hiding global synchronization latency in the preconditioned conjugate gradient algorithm, Parallel Comput., 40, 7, 224-238 (2014)
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.