A fast algorithm with error bounds for quadrature by expansion. (English) Zbl 1416.65072
Summary: Quadrature by expansion (QBX) is a quadrature method for approximating the value of the singular integrals encountered in the evaluation of layer potentials. It exploits the smoothness of the layer potential by forming locally-valid expansions which are then evaluated to compute the near or on-surface value of the potential. Recent work towards coupling of a fast multipole method (FMM) to QBX yielded a first step towards the rapid evaluation of such integrals (and the solution of related integral equations), albeit with only empirically understood error behavior. In this paper, we improve upon this approach with a modified algorithm for which we give a comprehensive analysis of error and cost in the case of the Laplace equation in two dimensions. For the same levels of (user-specified) accuracy, the new algorithm empirically has cost-per-accuracy comparable to prior approaches. We provide experimental results to demonstrate scalability and numerical accuracy.
MSC:
| 65D30 | Numerical integration |
| 65N38 | Boundary element methods for boundary value problems involving PDEs |
| 35J05 | Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation |
References:
| [1] | Atkinson, K. E.; Chien, D., Piecewise polynomial collocation for boundary integral equations, SIAM J. Sci. Comput., 16, 3, 651-681 (1995) · Zbl 0826.65095 |
| [2] | Atkinson, Kendall, A Survey of Numerical Methods for the Solution of Fredholm Integral Equations of the Second Kind (1976), Soc. for Industrial and Applied Mathematics · Zbl 0353.65069 |
| [3] | Barnes, Josh; Hut, Piet, A hierarchical O (N log N) force-calculation algorithm, Nature, 324, 6096, 446-449 (1986) |
| [4] | Barnett, Alexander H., Evaluation of layer potentials close to the boundary for Laplace and Helmholtz problems on analytic planar domains, SIAM J. Sci. Comput., 36, 2, A427-A451 (2014) · Zbl 1298.65184 |
| [5] | Beale, J. T.; Lai, M.-C., A method for computing nearly singular integrals, SIAM J. Sci. Comput., 38, 6, 1902-1925 (2001) · Zbl 0988.65025 |
| [6] | Biros, George; Ying, Lexing; Zorin, Denis, An embedded boundary integral solver for the unsteady incompressible Navier-Stokes equations, J. Comput. Phys., 121-141 (2004) · Zbl 1047.76065 |
| [7] | Bremer, J.; Gimbutas, Z.; Rokhlin, V., A nonlinear optimization procedure for generalized Gaussian quadratures, SIAM J. Sci. Comput., 32, 1761-1788 (2010) · Zbl 1215.65045 |
| [8] | Bremer, James, On the Nyström discretization of integral equations on planar curves with corners, Appl. Comput. Harmon. Anal., 32, 1, 45-64 (2012) · Zbl 1269.65131 |
| [9] | Bruno, O. P.; Kunyansky, L. A., A fast, high-order algorithm for the solution of surface scattering problems: basic implementation, tests, and applications, J. Comput. Phys., 169, 80-110 (2001) · Zbl 1052.76052 |
| [10] | Carley, M., Numerical quadratures for singular and hypersingular integrals in boundary element methods, SIAM J. Sci. Comput., 29, 3, 1207-1216 (2007) · Zbl 1141.65393 |
| [11] | Carrier, J.; Greengard, L.; Rokhlin, V., A fast adaptive multipole algorithm for particle simulations, SIAM J. Sci. Stat. Comput., 9, 4, 669-686 (1988) · Zbl 0656.65004 |
| [12] | Chapko, Roman; Kress, Rainer; Mönch, Lars, On the numerical solution of a hypersingular integral equation for elastic scattering from a planar crack, IMA J. Numer. Anal., 20, 4, 601-619 (Oct. 2000) · Zbl 0995.74080 |
| [13] | Christlieb, Andrew J., Grid-free plasma simulation techniques, IEEE Trans. Plasma Sci., 34, 2, 149-165 (2006) |
| [14] | Conway, John B., Functions of One Complex Variable, Graduate Texts in Mathematics, vol. 11 (1978), Springer-Verlag: Springer-Verlag New York-Berlin, pp. xiii+317 · Zbl 0277.30001 |
| [15] | Davis, P. J.; Rabinowitz, P., Methods of Numerical Integration (1984), Academic Press: Academic Press San Diego · Zbl 0537.65020 |
| [16] | Dehnen, Walter, A hierarchical O(N) force calculation algorithm, J. Comput. Phys., 179, 1, 27-42 (2002) · Zbl 1130.85303 |
| [17] | Epstein, Charles L.; Greengard, Leslie; Klöckner, Andreas, On the convergence of local expansions of layer potentials, SIAM J. Numer. Anal., 51, 5, 2660-2679 (2013) · Zbl 1281.65047 |
| [18] | Farina, L., Evaluation of single layer potentials over curved surfaces, SIAM J. Sci. Comput., 23, 1, 81-91 (2001) · Zbl 0990.65131 |
| [19] | Goodman, J.; Hou, T. Y.; Lowengrub, J., Convergence of the point vortex method for the 2-D Euler equations, Commun. Pure Appl. Math., 43, 415-430 (1990) · Zbl 0694.76013 |
| [21] | Greengard, Leslie, The Rapid Evaluation of Potential Fields in Particle Systems, ACM Distinguished Dissertations (1988), MIT Press: MIT Press Cambridge, MA, pp. xiv+91 · Zbl 1001.31500 |
| [22] | Greengard, Leslie; Rokhlin, Vladimir, A fast algorithm for particle simulations, J. Comput. Phys., 73, 2, 325-348 (1987) · Zbl 0629.65005 |
| [23] | Hackbusch, W.; Sauter, S. A., On numerical cubatures of nearly singular surface integrals arising in BEM collocation, Computing, 52, 2, 139-159 (1994) · Zbl 0799.65028 |
| [24] | Hao, S., High-order accurate methods for Nyström discretization of integral equations on smooth curves in the plane, Adv. Comput. Math., 40, 1, 245-272 (Feb. 2014) · Zbl 1300.65093 |
| [25] | Haroldsen, D. J.; Meiron, D. I., Numerical calculation of three-dimensional interfacial potential flows using the point vortex method, Commun. Pure Appl. Math., 43, 415-430 (1990) |
| [30] | Johnson, C. G.L.; Scott, L. R., An analysis of quadrature errors in second-kind boundary integral methods, SIAM J. Numer. Anal., 26, 6, 1356-1382 (1989) · Zbl 0695.65067 |
| [32] | af Klinteberg, Ludvig; Tornberg, Anna-Karin, Adaptive quadrature by expansion for layer potential evaluation in two dimensions, SIAM J. Sci. Comp., 40, 3, A1225-A1249 (2018) · Zbl 1446.65204 |
| [34] | Klöckner, Andreas, Quadrature by expansion: a new method for the evaluation of layer potentials, J. Comput. Phys., 252, 332-349 (2013) · Zbl 1349.65094 |
| [36] | Kußmaul, Rainer, Ein numerisches Verfahren zur Lösung des Neumannschen Außenraumproblems für die Helmholtzsche Schwingungsgleichung, Computing, 4, 3, 246-273 (1969) · Zbl 0187.40203 |
| [37] | Lowengrub, J.; Shelley, M.; Merriman, B., High-order and efficient methods for the vorticity formulation of the Euler equations, SIAM J. Sci. Comput., 14, 1107-1142 (1993) · Zbl 0815.76068 |
| [38] | Lyness, J. N.; Delves, L. M., On numerical contour integration round a closed contour, Math. Comput., 21, 100, 561-577 (Oct. 1967) · Zbl 0153.46603 |
| [39] | Martensen, Erich, Über eine Methode zum räumlichen Neumannschen Problem mit einer Anwendung für torusartige Berandungen, Acta Math., 109, 1, 75-135 (1963) · Zbl 0123.29004 |
| [40] | Mayo, A., Fast, high-order accurate solution of Laplace’s equation on irregular regions, SIAM J. Sci. Comput., 20, 648-683 (1998) |
| [41] | Moore, Doug, The cost of balancing generalized quadtrees, (Proceedings of the Third ACM Symposium on Solid Modeling and Applications. Proceedings of the Third ACM Symposium on Solid Modeling and Applications, SMA ’95, Salt Lake City, Utah, USA (1995), ACM), 305-312 |
| [42] | Petersen, Henrik G., Error estimates for the fast multipole method. I. The two-dimensional case, Proc. Math. Phys. Sci., 448, 1934, 389-400 (1995) · Zbl 0831.65135 |
| [43] | Pouransari, Hadi; Darve, Eric, Optimizing the adaptive fast multipole method for fractal sets, SIAM J. Sci. Comput., 37, 2, A1040-A1066 (2015) · Zbl 1316.28010 |
| [44] | Rachh, Manas, Integral Equation Methods for Problems in Electrostatics, Elastostatics and Viscous Flow (2015), New York University, PhD thesis |
| [45] | Manas Rachh, Andreas Klöckner, Leslie Greengard, Fast Algorithms for ‘Quadrature by Expansion’ II: Unidirectional Interactions, in preparation.; Manas Rachh, Andreas Klöckner, Leslie Greengard, Fast Algorithms for ‘Quadrature by Expansion’ II: Unidirectional Interactions, in preparation. |
| [46] | Rachh, Manas; Klöckner, Andreas; O’Neil, Michael, Fast algorithms for quadrature by expansion I: globally valid expansions, J. Comput. Phys., 345, 706-731 (2017) · Zbl 1378.65074 |
| [47] | Rahimian, Abtin; Barnett, Alex; Zorin, Denis, Ubiquitous evaluation of layer potentials using quadrature by kernel-independent expansion, BIT Numer. Math. (2017) · Zbl 1395.65151 |
| [48] | Rokhlin, Vladimir, Rapid solution of integral equations of classical potential theory, J. Comput. Phys., 60, 2, 187-207 (1985) · Zbl 0629.65122 |
| [49] | Saad, Youcef; Schultz, Martin H., GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7, 3, 856-869 (July 1986) · Zbl 0599.65018 |
| [50] | Schwab, C.; Wendland, W. L., On numerical cubatures of singular surface integrals in boundary element methods, Numer. Math., 62, 342-369 (1992) · Zbl 0761.65012 |
| [51] | Sidi, A.; Israeli, M., Quadrature methods for periodic singular Fredholm integral equations, J. Sci. Comput., 3, 201-231 (1988) · Zbl 0662.65122 |
| [52] | Siegel, Michael; Tornberg, Anna-Karin, A local target specific quadrature by expansion method for evaluation of layer potentials in 3D, J. Comput. Phys., 364, 365-392 (2018) · Zbl 1398.65356 |
| [53] | Strain, J., Locally-corrected multidimensional quadrature rules for singular functions, SIAM J. Sci. Comput., 16, 4, 992-1017 (1995) · Zbl 0828.65016 |
| [54] | White, C. A., The continuous fast multipole method, Chem. Phys. Lett., 230, 8-16 (Nov. 1994) |
| [55] | Yarvin, Nathan; Rokhlin, Vladimir, Generalized Gaussian quadratures and singular value decompositions of integral operators, SIAM J. Sci. Comput., 20, 2, 699-718 (1998) · Zbl 0932.65020 |
| [56] | 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 |
| [57] | Ying, Lexing; Biros, George; Zorin, Denis, A kernel-independent adaptive fast multipole algorithm in two and three dimensions, J. Comput. Phys., 196, 2, 591-626 (2004) · Zbl 1053.65095 |
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.
