A Kernel-Independent Sum-of-Exponentials Method

Springer Science and Business Media LLC - Tập 93 - Trang 1-35 - 2022
Zixuan Gao1, Jiuyang Liang1,2, Zhenli Xu1,2
1School of Mathematical Sciences, Shanghai Jiao Tong University, Shanghai, People’s Republic of China
2Institute of Natural Sciences, CMA-Shanghai and MOE-LSC, Shanghai Jiao Tong University, Shanghai, People’s Republic of China

Tóm tắt

We propose an accurate algorithm for a novel sum-of-exponentials (SOE) approximation of kernel functions, and develop a fast algorithm for convolution quadrature based on the SOE, which allows an order N calculation for N time steps of approximating a continuous temporal convolution integral. The SOE method is constructed by a combination of the de la Vallée-Poussin sum for a semi-analytical exponential expansion of a general kernel, and a model reduction technique to minimize the number of exponentials under a given error tolerance. We employ the SOE expansion for the finite part of the splitting convolution kernel so that the convolution integral can be solved as a system of ordinary differential equations. We show that the SOE method works for general kernels with controllable upperbound of positive exponents. Numerical analysis is provided for both the SOE method and the SOE-based convolution quadrature. Numerical results on different kernels demonstrate attractive performance on both accuracy and efficiency of the proposed method.

Tài liệu tham khảo

Beylkin, G., Kurcz, C., Monzón, L.: Fast convolution with the free space Helmholtz Green’s function. J. Comput. Phys. 228(8), 2770–2791 (2009) Cheng, H., Greengard, L., Rokhlin, V.: A fast adaptive multipole algorithm in three dimensions. J. Comput. Phys. 155(2), 468–498 (1999) Greengard, L., Jiang, S., Zhang, Y.: The anisotropic truncated kernel method for convolution with free-space Green’s functions. SIAM J. Sci. Comput. 40(6), A3733–A3754 (2018) Jiang, S., Greengard, L.: Efficient representation of nonreflecting boundary conditions for the time-dependent Schrödinger equation in two dimensions. Commun. Pure Appl. Math. 61(2), 261–288 (2008) Lubich, C., Schädle, A.: Fast convolution for nonreflecting boundary conditions. SIAM J. Sci. Comput. 24(1), 161–182 (2002) Gimbutas, Z., Marshall, N.F., Rokhlin, V.: A fast simple algorithm for computing the potential of charges on a line. Appl. Comput. Harmon. Anal. 49(3), 815–830 (2020) Jiang, S.: A fast Gauss transform in one dimension using sum-of-exponentials approximations, arXiv:1909.09825 Wang, B., Chen, D., Zhang, B., Zhang, W., Cho, M.H., Cai, W.: Taylor expansion based fast multipole method for 3-D Helmholtz equations in layered media. J. Comput. Phys. 401, 109008 (2020) Fang, D., Yang, J., Delisle, G.: Discrete image theory for horizontal electric dipoles in a multilayered medium, In: IEE Proceedings H-microwaves, Antennas and Propagation, Vol. 135, IET, 1988, pp. 297–303 Alparslan, A., Aksun, M.I., Michalski, K.A.: Closed-form Green’s functions in planar layered media for all ranges and materials. IEEE Trans. Microw. Theory Tech. 58(3), 602–613 (2010) Spivak, M., Veerapaneni, S.K., Greengard, L.: The fast generalized Gauss transform. SIAM J. Sci. Comput. 32(5), 3092–3107 (2010) Zhang, Y., Zhuang, C., Jiang, S.: Fast one-dimensional convolution with general kernels using sum-of-exponential approximation. Communications in Computational Physics 29(5), 1570–1582 (2021) Beylkin, G., Monzón, L.: On approximation of functions by exponential sums. Appl. Comput. Harmon. Anal. 19(1), 17–48 (2005) Beylkin, G., Monzón, L.: Approximation by exponential sums revisited. Appl. Comput. Harmon. Anal. 28(2), 131–149 (2010) Braess, D.: Asymptotics for the approximation of wave functions by exponential sums. J. Approx. Theory 83(1), 93–103 (1995) Braess, D., Hackbusch, W.: Approximation of \(1/x\) by exponential sums in \([1,\infty )\). IMA J. Numer. Anal. 25(4), 685–697 (2005) Braess, D., Hackbusch, W.: On the efficient computation of high-dimensional integrals and the approximation by exponential sums, In: Multiscale, nonlinear and adaptive approximation, Springer, 2009, pp. 39–74 Evans, J.W., Gragg, W.B., LeVeque, R.J.: On least squares exponential sum approximation with positive coefficients. Math. Comput. 34(149), 203–211 (1980) Gonchar, A.A., Rakhmanov, E.A.: Equilibrium distributions and degree of rational approximation of analytic functions. Mathematics of the USSR-Sbornik 62(2), 305 (1989) Hamming, R.: Numerical Methods for Scientists and Engineers. Courier Corporation, North Chelmsford, Massachusetts (2012) Wiscombe, W.J., Evans, J.W.: Exponential-sum fitting of radiative transmission functions. J. Comput. Phys. 24(4), 416–444 (1977) Boyd, J.P.: The uselessness of the fast Gauss transform for summing Gaussian radial basis function series. J. Comput. Phys. 229(4), 1311–1326 (2010) Lubich, C., Ostermann, A.: Runge-Kutta methods for parabolic equations and convolution quadrature. Math. Comput. 60(201), 105–131 (1993) Albtoush, R., Al-Khaled, K.: Approximation of periodic functions by Vallée Poussin sums. Hokkaido Math. J. 30(2), 269–282 (2001) de La Vallée-Poussin, C.J.: Leçons sur l’approximation des fonctions d’une variable réelle, Paris, (1919) Moore, B.: Principal component analysis in linear systems: controllability, observability, and model reduction. IEEE Trans. Autom. Control 26(1), 17–32 (1981) Benner, P., Gugercin, S., Willcox, K.: A survey of projection-based model reduction methods for parametric dynamical systems. SIAM Rev. 57(4), 483–531 (2015) Schädle, A., López-Fernández, M., Lubich, C.: Fast and oblivious convolution quadrature. SIAM J. Sci. Comput. 28(2), 421–438 (2006) Banjai, L., Lubich, C.: An error analysis of Runge-Kutta convolution quadrature. BIT Numer. Math. 51(3), 483–496 (2011) Liang, J., Gao, Z., Xu, Z.: A kernel-independent sum-of-Gaussians method by de la Vallee-Poussin sums. Adv. Appl. Math. Mech. 13(5), 1126–1141 (2021) Antoulas, A., Sorensen, D.: Approximation of large-scale dynamical systems: an overview. Int. J. Appl. Math. Comput. Sci. 11(5), 1093–1121 (2001) Jiang, S., Greengard, L.: Approximating the Gaussian as a sum of exponentials and its applications to the fast Gauss transform. Communications in Computational Physics 31(1), 1–26 (2022) Glover, K.: All optimal hankel-norm approximations of linear multivariable systems and their \({L}^\infty \)-error bounds. Int. J. Control 39(6), 1115–1193 (1984) Ober, R.: Balanced parametrization of classes of linear systems. SIAM J. Control. Optim. 29(6), 1251–1287 (1991) Multiprecision Computing Toolbox, Advanpix, Tokyo. http://www.advanpix.com Liu, W., Sreeram, V., Teo, K.L.: Model reduction for state-space symmetric systems. Systems & Control Letters 34(4), 209–215 (1998) Shampine, L.F.: Vectorized adaptive quadrature in MATLAB. J. Comput. Appl. Math. 211(2), 131–140 (2008) Occorsio, D., Serafini, G.: Cubature formulae for nearly singular and highly oscillating integrals. Calcolo 55(1), 1–33 (2018) Krishnamoorthy, A., Menon, D.: Matrix inversion using Cholesky decomposition, In: signal processing: Algorithms, architectures, arrangements, and applications (SPA). IEEE 2013, 70–72 (2013) Halko, N., Martinsson, P.-G., Tropp, J.A.: Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev. 53(2), 217–288 (2011) Rokhlin, V., Szlam, A., Tygert, M.: A randomized algorithm for principal component analysis. SIAM J. Matrix Anal. Appl. 31(3), 1100–1124 (2010) Sharapudinov, I.I.: Approximation properties of de la Vallée-Poussin means on classes of Sobolev type with variable exponent Vestn. Daghestan Res. Center Russian Academy of Sciences 45, 5–13 (2012) Magomed-Kasumov, M.G.: Approximation properties of de la Vallée-Poussin means for piecewise smooth functions. Math. Notes 100(1), 229–244 (2016) Huang, H., Marcantognini, S., Young, N.: Chain rules for higher derivatives. The Mathematical Intelligencer 28(2), 61–69 (2006) Spivak, M., Veerapaneni, S.K., Greengard, L.: The fast generalized Gauss transform. SIAM J. Sci. Comput. 32(5), 3092–3107 (2010) López-Fernández, M., Palencia, C., Schädle, A.: A spectral order method for inverting sectorial Laplace transforms. SIAM J. Numer. Anal. 44(3), 1332–1350 (2006) Trefethen, L.N., Weideman, J.A.C., Schmelzer, T.: Talbot quadratures and rational approximations. BIT Numer. Math. 46(3), 653–670 (2006) Talbot, A.: The accurate numerical inversion of Laplace transforms. IMA J. Appl. Math. 23(1), 97–120 (1979) Weideman, J., Trefethen, L.: Parabolic and hyperbolic contours for computing the bromwich integral. Math. Comput. 76(259), 1341–1356 (2007) Weideman, J.: Improved contour integral methods for parabolic PDEs. IMA J. Numer. Anal. 30(1), 334–350 (2010) Singh, S.: Prony Toolbox, MATLAB Central File Exchange Woodard, R.: Interpolation of spatial data: Some theory for kriging. Springer, Berlin (1999) Williams, C.K.I.: Gaussian Processes for Machine Learning. MIT Press, Cambridge (2005) Denzel, A., Kästner, J.: Gaussian process regression for geometry optimization. J. Chem. Phys. 148(9), 094114 (2018) Dral, P.O.: Gaussian process regression for geometry optimization. Journal on Computational Chemistry 40(26), 2339–2347 (2019) Ewald, P.P.: Die Berechnung optischer und elektrostatischer Gitterpotentiale. Ann. Phys. 369(3), 253–287 (1921) Jin, S., Li, L., Xu, Z., Zhao, Y.: A random batch Ewald method for particle systems with Coulomb interactions. SIAM J. Sci. Comput. 43(4), B937–B960 (2021) Liang, J., Tan, P., Zhao, Y., Li, L., Jin, S., Hong, L., Xu, Z.: Superscalability of the random batch Ewald method. J. Chem. Phys. 156(1), 014114 (2022) Colton, D.L., Kress, R., Kress, R.: Inverse acoustic and electromagnetic scattering theory, vol. 93. Springer, Berlin (1998) Engquist, B., Ying, L.: A fast directional algorithm for high frequency acoustic scattering in two dimensions. Commun. Math. Sci. 7(2), 327–345 (2009) Liang, J., Xu, Z., Zhou, Q.: Random batch sum-of-Gaussians method for molecular dynamics simulations of particle systems, arXiv:2205.13824 Lopez-Marcos, M.: A difference scheme for a nonlinear partial integro-differential equation. SIAM J. Numer. Anal. 27(1), 20–31 (1990) Sanz-Serna, J.M.: A numerical method for a partial integro-differential equation. SIAM J. Numer. Anal. 25(2), 319–327 (1988) Cao, J., Xu, C.: A high order schema for the numerical solution of the fractional ordinary differential equations. J. Comput. Phys. 238, 154–168 (2013) Cuesta, E., Palencia, C.: A fractional trapezoidal rule for integro-differential equations of fractional order in Banach spaces. Appl. Numer. Math. 45(2–3), 139–159 (2003) Banjai, L., López-Fernández, M.: Efficient high order algorithms for fractional integrals and fractional differential equations. Numer. Math. 141(2), 289–317 (2019) Li, J.-R.: A fast time stepping method for evaluating fractional integrals. SIAM J. Sci. Comput. 31(6), 4696–4714 (2010) Zakeri, G.-A., Navab, M.: Sinc collocation approximation of non-smooth solution of a nonlinear weakly singular Volterra integral equation. J. Comput. Phys. 229(18), 6548–6557 (2010) Lubich, C.: Fractional linear multistep methods for Abel-Volterra integral equations of the second kind. Math. Comput. 45(172), 463–469 (1985) Lubich, C.: Convolution quadrature and discretized operational calculus. I, Numerische Mathematik 52(2), 129–145 (1988) Lubich, C.: Convolution quadrature and discretized operational calculus. II, Numerische Mathematik 52(4), 413–425 (1988) Lubich, C.: Convolution quadrature revisited. BIT Numer. Math. 44(3), 503–514 (2004) López-Fernández, M., Sauter, S.: Generalized convolution quadrature with variable time stepping. IMA J. Numer. Anal. 33(4), 1156–1175 (2013) March, W. B., Xiao, B., Tharakan, S., Yu, C. D., Biros, G.: A kernel-independent FMM in general dimensions, in: SC ’15: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, 2015, pp. 1–12 Liao, S.: Beyond Perturbation: Introduction to The Homotopy Analysis Method. CRC Press, Boca Raton, FL (2003) Trujillo, J., Rivero, M., Bonilla, B.: On a Riemann-Liouville generalized Taylor’s formula. J. Math. Anal. Appl. 231(1), 255–265 (1999) Liu, Z., Wang, T., Gao, G.: A local fractional Taylor expansion and its computation for insufficiently smooth functions. East Asian Journal on Applied Mathematics 5(2), 176–191 (2015) Osler, T.J.: Taylor’s series generalized for fractional derivatives and applications. SIAM J. Math. Anal. 2(1), 37–48 (1971) Tongke, W., Meng, F.: Fractional order degenerate kernel methods for Fredholm integral equations of the second kind with endpoint singularities. Math. Numer. Sin. 41(1), 66 (2019) Guo, J., Wang, T.: Fractional Hermite degenerate kernel method for linear Fredholm integral equations involving endpoint weak singularities. Journal of Applied Analysis & Computation 10(5), 1918–1936 (2020) Zarei, E., Noeiaghdam, S.: Solving generalized Abel’s integral equations of the first and second kinds via Taylor-collocation method, arXiv preprint arXiv:1804.08571 Toutounian, F., Nasabzadeh, H.: A new method based on generalized Taylor expansion for computing a series solution of the linear systems. Appl. Math. Comput. 248, 602–609 (2014) Wanner, G., Hairer, E.: Solving Ordinary Differential Equations. Springer, Berlin Heidelberg (1996) Srivastava, H.M., Buschman, R.G.: Theory and Applications of Convolution Integral equations. Springer Science & Business Media, Berlin (2013) Corduneanu, C.: Integral Equations and Stability of Feedback Systems. Academic Press, Cambridge, Massachusetts (1973) Jaswon, M.A., Symm, G.T.: Integral Equation Methods in Potential Theory and Elastostatics. Academic Press, Cambridge, Massachusetts (1977) Jiang, S., Rokhlin, V.: Second kind integral equations for the classical potential theory on open surfaces II. J. Comput. Phys. 195(1), 1–16 (2004) der Heiden, U.: Analysis of Neural Networks, vol. 35. Springer Science & Business Media, Berlin (2013) Levinson, N.: A nonlinear Volterra equation arising in the theory of superfluidity. J. Math. Anal. Appl. 1(1), 1–11 (1960)