Wideband nested cross approximation for Helmholtz problems. (English) Zbl 1317.65242
Compared with explicit kernel approximation, significantly better approximations can be expected from the adaptive cross approximation (ACA) method of M. Bebendorf [Numer. Math. 86, No. 4, 565–589 (2000; Zbl 0966.65094)], due to the quasi-optimal approximation properties given by M. Bebendorf [Hierarchical matrices. A means to efficiently solve elliptic boundary value problems. Berlin: Springer (2008; Zbl 1151.65090)]. The authors generalizes ACA (which achieves log-linear complexity only for low-frequencies) to high-frequency Helmholtz problems by constructing approximations to A with complexity \(k^2 N \log N\) using only few of the original entries of A. It is interesting to observe that the method presented here allows for a continuous and numerically stable transition from low to high wave numbers \( \kappa\) by a generalized far-field condition that fades to the usual far-field condition if the wave number becomes small. It is also concluded that the log-linear overall storage and the log-linear number of operations are required by the new technique. To validate the analysis presented some numerical experiments are given.
Reviewer: H. P. Dikshit (Bhopal)
MSC:
| 65N38 | Boundary element methods for boundary value problems involving PDEs |
| 35J05 | Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation |
| 65Y20 | Complexity and performance of numerical algorithms |
Keywords:
adaptive cross approximation; high-frequency Helmholtz problems; generalized far-field condition; log-linear complexity; numerical experimentReferences:
| [1] | Alpert, B.K., Beylkin, G., Coifman, R., Rokhlin, V.: Wavelet-like bases for the fast solution of second-kind integral equations. SIAM J. Sci. Comput. 14, 159-184 (1993) · Zbl 0771.65088 · doi:10.1137/0914010 |
| [2] | Amini, S., Profit, A.: Multi-level fast multipole solution of the scattering problem. Eng. Anal. Bound. Elements 27(5), 547-654 (2003) · Zbl 1039.65084 · doi:10.1016/S0955-7997(02)00161-3 |
| [3] | Anderson, C.R.: An implementation of the fast multipole method without multipoles. SIAM J. Sci. Stat. Comput. 13(4), 923-947 (1992) · Zbl 0754.65101 · doi:10.1137/0913055 |
| [4] | Banjai, L., Hackbusch, W.: Hierarchical matrix techniques for low- and high-frequency Helmholtz problems. IMA J. Numer. Anal. 28(1), 46-79 (2008). doi:10.1093/imanum/drm001 · Zbl 1149.78009 · doi:10.1093/imanum/drm001 |
| [5] | Barnes, J., Hut, P.: A hierarchical \[\cal O({N}\log{N})O\](NlogN) force calculation algorithm. Nature 324, 446-449 (1986) · doi:10.1038/324446a0 |
| [6] | Bebendorf, M.: Approximation of boundary element matrices. Numer. Math. 86(4), 565-589 (2000) · Zbl 0966.65094 · doi:10.1007/PL00005410 |
| [7] | Bebendorf, M.: Hierarchical matrices: a means to efficiently solve elliptic boundary value problems. In: Lecture Notes in Computational Science and Engineering (LNCSE), vol. 63. Springer, Berlin (2008). ISBN 978-3-540-77146-3 · Zbl 1151.65090 |
| [8] | Bebendorf, M., Venn, R.: Constructing nested bases approximations from the entries of non-local operators. Numer. Math. 121(4), 609-635 (2012) · Zbl 1252.65206 · doi:10.1007/s00211-012-0449-9 |
| [9] | Börm, \[S.: {\cal H}^2\] H2-matrix arithmetics in linear complexity. Computing 77(1), 1-28 (2006) · Zbl 1086.65036 |
| [10] | Börm, S., Löhndorf, M., Melenk, J.M.: Approximation of integral operators by variable-order interpolation. Numer. Math. 99(4), 605-643 (2005) · Zbl 1076.65121 · doi:10.1007/s00211-004-0564-3 |
| [11] | Brakhage, H., Werner, P.: Über das Dirichletsche Außenraumproblem für die Helmholtzsche Schwingungsgleichung. Arch. Math. 16, 325-329 (1965) · Zbl 0132.33601 · doi:10.1007/BF01220037 |
| [12] | Brandt, A.: Multilevel computations of integral transforms and particle interactions with oscillatory kernels. Comput. Phys. Commun. 65, 24-38 (1991) · Zbl 0900.65121 · doi:10.1016/0010-4655(91)90151-A |
| [13] | Buffa, A., Hiptmair, R.: A coercive combined field integral equation for electromagnetic scattering. SIAM J. Numer. Anal. 42(2), 621-640 (2003) · Zbl 1082.78003 · doi:10.1137/S0036142903423393 |
| [14] | Burton, A.J., Miller, G.F.: The application of integral equation methods to the numerical solution of boundary value problems. Proc. R. Soc. Lond. A232, 201-210 (1971) · Zbl 0235.65080 · doi:10.1098/rspa.1971.0097 |
| [15] | Candès, E., Demanet, L., Ying, L.: A fast butterfly algorithm for the computation of Fourier integral operators. Multiscale Model. Simul. 7(4), 1727-1750 (2009). doi:10.1137/080734339 · Zbl 1184.65125 · doi:10.1137/080734339 |
| [16] | Chandler-Wilde, S.N., Graham, I.G., Langdon, S., Spence, E.A.: Numerical-asymptotic boundary integral methods in high-frequency acoustic scattering. Acta Numerica 21, 89-305 (2012) · Zbl 1257.65070 · doi:10.1017/S0962492912000037 |
| [17] | Cheng, H., Crutchfield, W.Y., Gimbutas, Z., Greengard, L.F., Ethridge, J.F., Huang, J., Rokhlin, V., Yarvin, N., Zhao, J.: A wideband fast multipole method for the Helmholtz equation in three dimensions. J. Comput. Phys. 216(1), 300-325 (2006). doi:10.1016/j.jcp.2005.12.001 · Zbl 1093.65117 · doi:10.1016/j.jcp.2005.12.001 |
| [18] | Darve, E.: The fast multipole method: numerical implementation. J. Comput. Phys. 160(1), 195-240 (2000) · Zbl 0974.78012 · doi:10.1006/jcph.2000.6451 |
| [19] | Engquist, B., Ying, L.: Fast directional multilevel algorithms for oscillatory kernels. SIAM J. Sci. Comput. 29(4), 1710-1737 (2007, electronic) · Zbl 1180.65006 |
| [20] | Engquist, B., Ying, L.: A fast directional algorithm for high frequency acoustic scattering in two dimensions. Commun. Math. Sci. 7(2), 327-345 (2009) · Zbl 1182.65178 · doi:10.4310/CMS.2009.v7.n2.a3 |
| [21] | Francia, G.T.D.: Degrees of freedom of an image. J. Opt. Soc. Am. 59(7), 799-803 (1969) · doi:10.1364/JOSA.59.000799 |
| [22] | Giebermann, K.: Schnelle Summationsverfahren zur numerischen Lösung von Integralgleichungen für Streuprobleme im \[\mathbb{R}^3\] R3. Ph.D. thesis, Universität Karlsruhe (1997) · Zbl 0930.65130 |
| [23] | Grasedyck, L., Hackbusch, W.: Construction and arithmetics of \[{\cal H}H\]-matrices. Computing 70, 295-334 (2003) · Zbl 1030.65033 · doi:10.1007/s00607-003-0019-1 |
| [24] | Greengard, L.: The Rapid Evaluation of Potential Fields in Particle Systems. MIT Press, Cambridge (1988) · Zbl 1001.31500 |
| [25] | Greengard, L.F., Rokhlin, V.: A fast algorithm for particle simulations. J. Comput. Phys. 73(2), 325-348 (1987) · Zbl 0629.65005 · doi:10.1016/0021-9991(87)90140-9 |
| [26] | Greengard, L.F., Rokhlin, V.: A new version of the fast multipole method for the Laplace equation in three dimensions. In: Acta Numerica, vol. 6, pp. 229-269. Cambridge University Press, Cambridge (1997) · Zbl 0889.65115 |
| [27] | Hackbusch, W.: A sparse matrix arithmetic based on \[\cal HH\]-matrices. Part I: introduction to \[\cal HH\]-matrices. Computing 62(2), 89-108 (1999) · Zbl 0927.65063 · doi:10.1007/s006070050015 |
| [28] | Hackbusch, W., Börm, S.: Data-sparse approximation by adaptive \[{\cal H}^2\] H2-matrices. Computing 69(1), 1-35 (2002) · Zbl 1012.65023 |
| [29] | Hackbusch, W., Khoromskij, B.N.: A sparse \[\cal HH\]-matrix arithmetic: general complexity estimates. J. Comput. Appl. Math. 125(1-2), 479-501 (2000). Numerical analysis 2000, vol. VI, Ordinary differential equations and integral equations · Zbl 0977.65036 |
| [30] | Hackbusch, W., Khoromskij, B.N.: A sparse \[\cal HH\]-matrix arithmetic. Part II: application to multi-dimensional problems. Computing 64(1), 21-47 (2000) · Zbl 0962.65029 |
| [31] | Hackbusch, W., Khoromskij, B.N., Sauter, S.A.: On \[{\cal H}^2\] H2-matrices. In: Bungartz, H.J., Hoppe, R.H.W., Zenger, C. (eds.) Lectures on Applied Mathematics, pp. 9-29. Springer, Berlin (2000) · Zbl 0963.65043 |
| [32] | Hackbusch, W., Nowak, Z.P.: On the fast matrix multiplication in the boundary element method by panel clustering. Numer. Math. 54(4), 463-491 (1989) · Zbl 0641.65038 · doi:10.1007/BF01396324 |
| [33] | Messner, M., Schanz, M., Darve, E.: Fast directional multilevel summation for oscillatory kernels based on Chebyshev interpolation. J. Comput. Phys. 231, 1175-1196 (2012) · Zbl 1239.65002 · doi:10.1016/j.jcp.2011.09.027 |
| [34] | Michielssen, E., Boag, A.: A multilevel matrix decomposition for analyzing scattering from large structures. IEEE Trans. Antennas Propag. 44, 1086-1093 (1996) · doi:10.1109/8.511816 |
| [35] | Rokhlin, V.: Rapid solution of integral equations of classical potential theory. J. Comput. Phys. 60(2), 187-207 (1985) · Zbl 0629.65122 · doi:10.1016/0021-9991(85)90002-6 |
| [36] | Rokhlin, V.: Rapid solution of integral equations of scattering theory in two dimensions. J. Comput. Phys. 86(2), 414-439 (1990) · Zbl 0686.65079 · doi:10.1016/0021-9991(90)90107-C |
| [37] | Rokhlin, V.: Diagonal forms of translation operators for the Helmholtz equation in three dimensions. Appl. Comput. Harmon. Anal. 1(1), 82-93 (1993) · Zbl 0795.35021 · doi:10.1006/acha.1993.1006 |
| [38] | Sauer, T., Xu, Y.: On multivariate Lagrange interpolation. Math. Comput. 64(211), 1147-1170 (1995) · Zbl 0823.41002 · doi:10.1090/S0025-5718-1995-1297477-5 |
| [39] | Tyrtyshnikov, E.E.: Mosaic-skeleton approximations. Calcolo 33(1-2), 47-57 (1998). Toeplitz matrices: structures, algorithms and applications (Cortona, 1996) · Zbl 0906.65048 |
| [40] | Ying, L., Biros, G., Zorin, D.: A kernel-independent adaptive fast multipole algorithm in two and three dimensions. J. Comput. Phys. 196(2), 591-626 (2004) · Zbl 1053.65095 · doi:10.1016/j.jcp.2003.11.021 |
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.
