×

Fast discrete convolution in \(\mathbb{R}^2\) with radial kernels using non-uniform fast Fourier transform with nonequispaced frequencies. (English) Zbl 1431.65252

Let \(z_k\in {\mathbb R}^2\) be given points of the unit disk and \(f_k\in \mathbb C\), \(k=1,\ldots,N\). Further, \(\|x\|\) is the Euclidean norm of \(x\in {\mathbb R}^2\). Let \(g:(0,\infty) \to \mathbb R\) be given. Later \(g(t)\) is chosen as \(\log t\), \(t^2 \log t\), and \(t^{-2}\), \(t>0\). In this paper, the author presents a new algorithm, the so-called efficient Bessel decomposition (EBD), for the fast evaluation of discrete convolutions with the radial kernel \(g(\|x\|)\) of the form \[ q_k = \sum_{\ell=1}^N g(\|z_k -z_{\ell}\|)\,f_{\ell}\,, \quad k = 1,\ldots,N\,. \] Using a trigonometric approximation of \(g(\|x\|)\), the discrete convolution can be rapidly computed by non-uniform fast Fourier transforms, see [D. Potts et al., Numer. Math. 98, No. 2, 329–351 (2004; Zbl 1056.65146)]. The new EBD method approximates \(g(\|x\|)\) by a Bessel series outside the origin by a small number \(P\) of terms \[ g(\|x\|) \approx g(1) + \sum_{n=1}^P \alpha_n\,J_0(\rho_n \|x\|)\,, \quad \delta \le \|x\|\le 1\,, \] where \(J_0\) is the Bessel function of first kind, \(\rho_n\) is the \(n\)th positive zero of \(J_0\), and \(\delta >0\) is a cutoff parameter. Applying the trapezoidal rule to the integral \[ J_0(\rho_n \|x\|) = \frac{1}{2\pi} \int_{\|y\|=1} {\mathrm e}^{{\mathrm i}\rho_n\,x\cdot y}\,{\mathrm d}y\,, \] the author obtains a trigonometric approximation of \(g(\|x\|)\). An important consequence of EBD is the fact that much less terms last for a given accuracy. This allows for a faster evaluation of the discrete convolution at the cost of longer precomputation. A Matlab code of this method is available online. The computational cost and the error of the EBD method are estimated. Numerical results are presented too.

MSC:

65T50 Numerical methods for discrete and fast Fourier transforms
33C10 Bessel and Airy functions, cylinder functions, \({}_0F_1\)
41A55 Approximate quadratures

Citations:

Zbl 1056.65146

Software:

Matlab; NFFT; DLMF; GitHub; NUFFT; EBD; NFFT3
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] NFFT project. See https://www-user.tu-chemnitz.de/potts/nfft/download.php
[2] NUFFT package. See https://cims.nyu.edu/cmcl/nufft/nufft.html
[3] Abramowitz, M., Stegun, I.A.: Handbook of mathematical functions: with formulas, graphs, and mathematical tables, vol. 55, Courier Corporation (1964) · Zbl 0171.38503
[4] Alouges, F.; Aussal, M., The sparse cardinal sine decomposition and its application for fast numerical convolution, Numer. Algorithms, 70, 2, 427-448 (2015) · Zbl 1326.65183 · doi:10.1007/s11075-014-9953-6
[5] Averseng, M.: EBD toolbox. See https://github.com/MartinAverseng/EBD
[6] Bentley, Jl, Multidimensional binary search trees used for associative searching, Commun. ACM, 18, 9, 509-517 (1975) · Zbl 0306.68061 · doi:10.1145/361002.361007
[7] Bentley, Jl; Stanat, Df; Williams, Eh, The complexity of finding fixed-radius near neighbors, Inf. Process. Lett., 6, 6, 209-212 (1977) · Zbl 0373.68041 · doi:10.1016/0020-0190(77)90070-9
[8] Cheng, H.; Greengard, L.; Rokhlin, V., A fast adaptive multipole algorithm in three dimensions, J. Comput. Phys., 155, 2, 468-498 (1999) · Zbl 0937.65126 · doi:10.1006/jcph.1999.6355
[9] Coifman, R.; Rokhlin, V.; Wandzura, S., The fast multipole method for the wave equation: a pedestrian prescription, IEEE Antennas Propag. Mag., 35, 3, 7-12 (1993) · doi:10.1109/74.250128
[10] Cooley, Jw; Tukey, Jw, An algorithm for the machine calculation of complex fourier series, Math. Comput., 19, 90, 297-301 (1965) · Zbl 0127.09002 · doi:10.1090/S0025-5718-1965-0178586-1
[11] Dickerson, Mt; Drysdale, Rs, Fixed-radius near neighbors search algorithms for points and segments, Inf. Process. Lett., 35, 5, 269-273 (1990) · Zbl 0703.68096 · doi:10.1016/0020-0190(90)90056-4
[12] Dutt, A.; Rokhlin, V., Fast fourier transforms for nonequispaced data, SIAM J. Sci Comput., 14, 6, 1368-1393 (1993) · Zbl 0791.65108 · doi:10.1137/0914081
[13] Grebenkov, D.; Nguyen, B-T, Geometrical structure of laplacian eigenfunctions, SIAM Rev., 55, 4, 601-667 (2013) · Zbl 1290.35157 · doi:10.1137/120880173
[14] Greengard, L., The Rapid Evaluation of Potential Fields in Particle Systems (1988), Cambridge: MIT Press, Cambridge · Zbl 1001.31500
[15] Greengard, L.; Lee, Jy, Accelerating the nonuniform fast fourier transform, SIAM Rev., 46, 3, 443-454 (2004) · Zbl 1064.65156 · doi:10.1137/S003614450343200X
[16] Keiner, J.; Kunis, S.; Potts, D., Using nfft 3—a software library for various nonequispaced fast fourier transforms, ACM Trans. Math. Softw. (TOMS), 36, 4, 19 (2009) · Zbl 1364.65303 · doi:10.1145/1555386.1555388
[17] Lee, June-Yub; Greengard, Leslie, The type 3 nonuniform fft and its applications, J. Comput. Phys., 206, 1, 1-5 (2005) · Zbl 1072.65170 · doi:10.1016/j.jcp.2004.12.004
[18] Olver, F.W.J., Olde Daalhuis, A.B., Lozier, D.W., Schneider, B.sI., Boisvert, R.F., Clark, C.W., Miller, B.R., Saunders, B.V.: NIST Digital Library of Mathematical Functions. http://dlmf.nist.gov/,Release1.0.16of2017-09-18
[19] Potts, D., Pöplau, G., Van Rienen, U.: Calculation of 3D Space-Charge Fields of Bunches of Charged Particles by Fast Summation. In: Scientific Computing in Electrical Engineering, vol. 11, pp. 241-246. Springer (2006) · Zbl 1157.78314
[20] Potts, D.; Steidl, G.; Nieslony, A., Fast convolution with radial kernels at nonequispaced knots, Numer. Math., 98, 2, 329-351 (2004) · Zbl 1056.65146 · doi:10.1007/s00211-004-0538-5
[21] Potts, D., Steidl, G., Tasche, M.: Fast Fourier transforms for nonequispaced data: a tutorial. In: Modern Sampling Theory, pp. 247-270. Springer (2001)
[22] 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
[23] 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
[24] Tolstov, G.P.: Fourier series. Courier Corporation (2012)
[25] Turau, V., Fixed-radius near neighbors search, Inf. Process. Lett., 39, 4, 201-203 (1991) · Zbl 0735.68091 · doi:10.1016/0020-0190(91)90180-P
[26] Watson, Gn, A Treatise on the Theory of Bessel Functions (1995), Cambridge: Cambridge University Press, Cambridge · Zbl 0849.33001
[27] Wilcox, Ch, Scattering Theory for the d’Alembert Equation in Exterior Domains, vol. 4 (1975), Berlin: Springer, Berlin · Zbl 0299.35002
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.