On fast multipole methods for Volterra integral equations with highly oscillatory kernels. (English) Zbl 1524.65991
Summary: This paper explores the fast multipole methods (FMMs) to accelerate the approximation for weakly singular Volterra integral equations with highly oscillatory trigonometric kernels. By constructing the fast translation path, the FMM is utilized to speed up the iterative method, which reduces the complexity from \(O(N^2)\) to \(O(N)\). Especially, we use the collocation method to discretize the Volterra integral equation with constants and linear elements respectively, then apply the GMRES to solve the dense and non-symmetric linear system. In addition, the highly oscillatory integrals derived from the algorithm are calculated effectively by the steepest descent method. The proposed method shows that the numerical solutions become more accurate as the frequency increases. Both of the optimal convergence rates of truncation and the error bounds analysis are represented in the end.
MSC:
| 65R20 | Numerical methods for integral equations |
| 45D05 | Volterra integral equations |
| 41A55 | Approximate quadratures |
| 65D32 | Numerical quadrature and cubature formulas |
Keywords:
fast multipole method; Volterra integral equation; weak singularity; highly oscillatory integrals; steepest descent methodReferences:
| [1] | Aleksandrov, V. M.; Kovalenko, E. V., Mathematical method in the displacement problem, Inzh. Zh. Mekh. Tverd. Tela., 2, 77-89, (1984) · Zbl 0588.73199 |
| [2] | Biazar, J.; Eslami, M.; Aminikhah, H., Application of homotopy perturbation method for systems of Volterra integral equations of the first kind, Chaos Solitons Fractals, 42, 3020-3026, (2009) · Zbl 1198.65254 |
| [3] | Biazar, J.; Ghazvini, H.; Eslami, M., He’s homotopy perturbation method for systems of integro-differential equations, Chaos Solitons Fractals, 39, 1253-1258, (2009) · Zbl 1197.65106 |
| [4] | Asheim, A.; Huybrechs, D., Local solutions to high frequency 2D scattering problems, J. Comput. Phys., 229, 5357-5372, (2009) · Zbl 1196.65181 |
| [5] | Colton, D.; Kress, R., Integral Equation Methods in Scattering Theory, (1983), Wiley: Wiley New York · Zbl 0522.35001 |
| [6] | Langdon, S.; Chandler-Wilde, S. N., A wavenumber independent boundary element method for an acoustic scattering problem, SIAM J. Numer. Anal., 43, 2450-2477, (2006) · Zbl 1108.76047 |
| [7] | Ndlec, J. C., (Acoustic and Electromagnetic Equations, Appl. Math. Sci, 144, (2001), Springer: Springer Berlin) · Zbl 0981.35002 |
| [8] | H. Brunner, On the numerical solution of first-kind Volterra integral equations with highly oscillatory kernels, September, 2010: Highly Oscillatory Problems: From Theory to Applications, HOP 13-17, Isaac Newton Institute.; H. Brunner, On the numerical solution of first-kind Volterra integral equations with highly oscillatory kernels, September, 2010: Highly Oscillatory Problems: From Theory to Applications, HOP 13-17, Isaac Newton Institute. |
| [9] | Herman, J. J.; Riele, T., Collocation methods for weakly singular second-kind Volterra integral equations with non-smooth solution, IMA J. Numer. Anal., 2, 437-449, (1982) · Zbl 0501.65062 |
| [10] | Eslami, M., New homotopy perturbation method for a special kind of Volterra integral equations in two-dimensional space, Comput. Math. Modeling, 25, 135-148, (2014) · Zbl 1327.65278 |
| [11] | Renz, D. M.; Böttcher, J.; T. Baltzer, P. A., Differential transform method for systems of Volterra integral equations of the second kind and comparison with homotopy perturbation method, Int. J. Phys. Sci., 120, 449-459, (2011) |
| [12] | H. Brunner, A. Iserles, S. Nørsett, Open problems in the computational solution of Volterra functional equations with highly oscillatory kernels, in: Effective Computational Methods for Highly Oscillatory Solutions, HOP 2007, Isaac Newton Institute.; H. Brunner, A. Iserles, S. Nørsett, Open problems in the computational solution of Volterra functional equations with highly oscillatory kernels, in: Effective Computational Methods for Highly Oscillatory Solutions, HOP 2007, Isaac Newton Institute. |
| [13] | Xiang, S.; Brunner, H., Efficient methods for Volterra integral equations with highly oscillatory Bessel kernels, BIT, 53, 241-263, (2013) · Zbl 1268.65171 |
| [14] | Xiang, S.; Wu, Q., Numerical solutions to Volterra integral equations of the second kind with oscillatory trigonometric kernels, Appl. Math. Comput., 223, 34-44, (2013) · Zbl 1329.65324 |
| [15] | Wu, Q., On graded meshes for weakly singular Volterra integral equations with oscillatory trigonometric kernels, J. Comput. Appl. Math., 263, 370-376, (2014) · Zbl 1301.65135 |
| [16] | Ma, J.; Fang, C.; Xiang, S., Modified asymptotic orders of the direct Filon method for a class of Volterra integral equations, J. Comput. Appl. Math., 281, 120-125, (2015) · Zbl 1310.65170 |
| [17] | Wang, H.; Xiang, S., Asymptotic expansion and Filon-type methods for a Volterra integral equation with a highly oscillatory kernel, IMA J. Numer. Anal., 31, 469-490, (2011) · Zbl 1242.65290 |
| [18] | Xiang, S., Laplace transforms for approximation of highly oscillatory Volterra integral equations of the first kind, Appl. Math. Comput., 232, 944-954, (2014) · Zbl 1410.65509 |
| [19] | Xiang, S.; He, K., On the implementation of discontinuous Galerkin methods for Volterra integral equations with highly oscillatory Bessel kernels, Appl. Math. Comput., 219, 4884-4891, (2013) · Zbl 1460.65167 |
| [20] | Rokhlin, V., Rapid solution of integral equations of classic potential theory, J. Comput. Phys., 60, 187-207, (1985) · Zbl 0629.65122 |
| [21] | Greengard, L.; Rokhlin, V., A fast algorithm for particle simulations, Comput. Phys., 73, 325-348, (1987) · Zbl 0629.65005 |
| [22] | Liu, Y., Fast Multipole Boundary Elementmethod: Theory and Applications in Engineering, (2009), Cambridge University Press: Cambridge University Press Cambridge |
| [23] | Grengard, L. F.; Rokhlin, V., The Rapid Evaluation of Potential Fields in Particle Systems in Paticale Systems, (1988), MIT Press: MIT Press Cambridge, MA · Zbl 1001.31500 |
| [24] | Dutt, A.; Gu, M.; Rokhlin, V., Fast algorithms for polynomial interpolation, integration, and differentiation, SIAM J. Numer. Anal., 33, 1689-1711, (1996) · Zbl 0862.65005 |
| [25] | Liu, G.; Xiang, S., Fast multipole methods for approximating a function from sampling values, Numer. Algorithms, 76, 1-17, (2017) |
| [26] | Yarvin, N.; Rokhlin, V., An improved fast multipole algorithm for potential fields on the line, SIAM J. Numer. Anal., 36, 629-666, (1999) · Zbl 0973.65106 |
| [27] | Rodriguez, J. L.; Taboada, J. M.; Araujo, M. G., On the use of the singular value decomposition in the fast multipole method, IEEE Trans. Antennas. Propagat., 56, 2325-2334, (2008) · Zbl 1369.78627 |
| [28] | Nishimura, N., Fast multipole accelerated boundary integral equation methods, Appl. Mech. Rev., 55, 299-324, (2002) |
| [29] | Shen, L.; Liu, Y., An adaptive fast multipole boundary element method for three-dimensional acoustic wave problems based on the BurtonCMiller formulation, Comput. Mech., 40, 461-472, (2007) · Zbl 1176.76083 |
| [30] | Greengard, L.; Rokhlin, V., A new version of the fast multipole method for the Laplace equation in three dimensions, Acta Numer., 6, 229-269, (1997) · Zbl 0889.65115 |
| [31] | Martinsson, P. G.; Rokhlin, V., An accelerated kernel-independent fast multipole method in one dimension, SIAM J. Sci. Comput., 29, 1160-1178, (2007) · Zbl 1154.65318 |
| [32] | Abramowitz, M.; Stegun, I. A., Handbook of Mathematical Functions, (1964), National Bureau of Standards: National Bureau of Standards Washington DC · Zbl 0171.38503 |
| [33] | Clenshaw, C. W.; Curtis, A. R., Amethod for numerical integration on an automatic computer, Numer. Math., 2, 197-205, (1960) · Zbl 0093.14006 |
| [34] | Xiang, S.; Chen, X.; Wang, H., Error bounds for approximation in Chebyshev points, Numer. Math., 116, 463-491, (2010) · Zbl 1201.65040 |
| [35] | Iserles, A.; Nørsett, S. P., Efficient quadrature of highly oscillatory integrals using derivatives, Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 461, 1383-1399, (2005) · Zbl 1145.65309 |
| [36] | Xiang, S., Efficient Filon-type methods for \(\int_a^b f(x) e^{i \omega g(x) d x}\), Numer. Math., 105, 633-658, (2007) · Zbl 1158.65020 |
| [37] | Olver, S., Moment-free numerical integration of highly oscillatory functions, IMA J. Numer. Anal., 26, 213-227, (2006) · Zbl 1106.65021 |
| [38] | Milovanovíc, G. V., Numerical calculation of integrals involving oscillatory and singular kernels and some applications of quadratures, Comput. Math. Appl., 36, 19-39, (1998) · Zbl 0932.65023 |
| [39] | Wang, H.; Xiang, S., On the evaluation of Cauchy principal value integrals of oscillatory functions, J. Comput. Appl. Math., 234, 95-100, (2010) · Zbl 1190.65043 |
| [40] | Kang, H.; Xiang, S., On the calculation of highly oscillatory integrals with an algebraic singularity, Appl. Math. Comput., 217, 3890-3897, (2010) · Zbl 1209.65030 |
| [41] | Huybrechs, D.; Vandewalle, S., On the evaluation of highly oscillatory integrals by analytic continuation, SIAM J. Numer. Anal., 44, 1026-1048, (2006) · Zbl 1123.65017 |
| [42] | Kang, H.; Shao, X., Fast computation of singular oscillatory fourier transforms, Abstr. Appl. Anal., 1, 1-8, (2014) · Zbl 1474.65523 |
| [43] | Xiang, S.; Liu, G., On optimal convergence rates of a two-dimensional fast multipole method, Appl. Math. Lett., 76, 74-80, (2018) · Zbl 1377.65164 |
| [44] | Stein, E., Harmonic Analysis: Real-Variable Methods, Orthogonality, and Oscillatory Integrals, (1993), Princeton University Press: Princeton University Press Princeton · Zbl 0821.42001 |
| [45] | Brunner, H., Collocation Methods for Volterra Integral and Related Functional Equations, (2004), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1059.65122 |
| [46] | Polyanin, A. D.; Manzhirov, A. V., Handbook of Integral Equations, (2008), CRC Press · Zbl 1154.45001 |
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.
