The sparse cardinal sine decomposition and its application for fast numerical convolution

详细信息    查看全文

• 作者：Fran?ois Alouges ; Matthieu Aussal
• 关键词：Quadrature ; Non uniform FFT ; Fast convolution ; Fast multipole method ; 65T50 ; 65Z05
• 刊名：Numerical Algorithms
• 出版年：2015
• 出版时间：October 2015
• 年：2015
• 卷：70
• 期：2
• 页码：427-448
• 全文大小：1,989 KB
• 参考文献：1.Acton, F.S.: Numerical Methods That Work. Math. Assoc. Amer., Washington D.C. (1990)
  2.Arnold, A., Fahrenberger, F., Holm, C., Lenz, O., Bolten, M., Dachsel, H., Halver, R., Kabadshow, I., G?hler, F., Heber, F., Iseringhausen, J., Hofmann, M., Pippig, M., Potts, D., Sutmann, G.: Comparison of scalable fast methods for long-range interactions. Phys. Rev. E 88, 063308 (2013)
  3.Chaillat, S., Bonnet, M.: A new fast multipole formulation for the elastodynamic half-space green’s tensor. J. Comput. Phys. 256, 787-08 (2014)MathSciNet CrossRef
  4.See http://?www.?cims.?nyu.?edu/?cmcl/?cmcl.?html
  5.Dutt, A., Rokhlin, V.: Fast Fourier transforms for nonequispaced data. SIAM J. Sci. Comput., 14 (1993)
  6.Elbel, B., Steidl, G.: Fast fourier transforms for nonequispaced data. In: Chui, C.K., Schumaker, L.L. (eds.) Approximation Theory IX, pp. 39-6. Vanderbilt University Press, Nashville (1998)
  7.Eremenko, A., Yuditskii, P.: Uniform approximation of sgn(x) by polynomials and entire functions. J. Anal. Math. 101, 313-24 (2007)MathSciNet CrossRef
  8.Ewald, P.: Dir Berechnung optischer und elektrostatischer Gitterpotentiale. In Ann. Phys. 369, 253-87 (1921)CrossRef
  9.Fliege, J., Maier, U.: A two-stage approach for computing cubature formulae for the sphere. In Mathematik 139T, Universitat Dortmund, Fachbereich Mathematik, Universitat Dortmund, 44221 (1996)
  10.Greengard, L., Lin, P.: Spectral approximation of the free-space heat kernel. Appl. Comput. Harmonic Anal. 9, 83-7 (2000)MathSciNet CrossRef
  11.Greengard, L.: The rapid evaluation of potential fields in particle systems. MIT Press (1988)
  12.Hesse, K., Sloan I.H., Womersley, R.S.: Numerical integration on the sphere. In: Handbook of Geomathematics, pp. 1185-219. Springer (2010)
  13.Hackbusch, W.: Hierarchische Matrizen. Springer (2009)
  14.Hamming, R.W. Numerical Methods for Scientists and Engineers, 2nd Ed. Dover, New York (1986)
  15.Kahaner, D., Moler, C., Nash, S.: Numerical methods and software. Prentice-Hall (1989)
  16.Lebedev, V.I., Laikov, D.N.: A quadrature formula for the sphere of the 131st algebraic order of accuracy. Dokl. Math. 59(3), 477-81 (1999)
  17.Lee, J.-Y., Greengard, L.: Accelerating the nonuniform fast Fourier transform. SIAM Rev. 48, 443-54 (2004)MathSciNet
  18.Lee, J.-Y., Greengard, L.: The type 3 nonuniform fft and its application. J. Comput. Phys. 206, 1- (2005)MathSciNet CrossRef
  19.See http://?www.?cims.?nyu.?edu/?cmcl/?nufft/?nufft.?html
  20.See http://?www.?cims.?nyu.?edu/?cmcl/?fmm3dlib/?fmm3dlib.?html
  21.Pippig, M., Potts, D.: Particle simulation based on nonequispaced fast Fourier transforms. In: Fast Methods for Long-Range Interactions in Complex Systems, IAS-Series, pp. 131-58. Forschungszentrum Jülich (2011)
  22.See http://?www-user.?tu-chemnitz.?de/?~potts/?nfft/-/span>
  23.Potts, D., Steidl, G., Nieslony, A.: Fast convolution with radial kernels at nonequispaced knots. Numer. Math. 98, 329-51 (2004)MathSciNet CrossRef
  24.Weisstein, E.W.: Lanczos σ factor. Mathworld-A Wolfram Web Resource. http://?mathworld.?wolfram.?com/?LanczosSigmaFact?or.?html
  25.Zolotarev, E.I.: Application of the elliptic functions to questions on functions of least and most deviation from zero. Bull. de l’Académie de Sci. de St.-Petersbourg 24(3) (1878)
  
• 作者单位：Fran?ois Alouges (1)
  Matthieu Aussal (1) (2)
  
  1. CMAP - Ecole Polytechnique, Route de Saclay, 91128, Palaiseau Cedex, France
  2. Digital Media Solutions, 45 Grande Allée du 12 Février 1934, 77186, Noisiel, France
  
• 刊物类别：Computer Science
• 刊物主题：Numeric Computing
  Algorithms
  Mathematics
  Algebra
  Theory of Computation
  
• 出版者：Springer U.S.
• ISSN：1572-9265

文摘

Fast convolution algorithms on unstructured grids have become a well established subject. Algorithms such as Fast Multipole Method (FMM), Adaptive Cross Approximation (ACA) or \(\mathcal {H}\)-matrices for instance are, by now, classical and reduce the complexity of the matrix-vector product from O(N 2) to O(N log N) with a broad range of applications in e.g. electrostatics, magnetostatics, acoustics or electromagnetics. In this paper we describe a new algorithm of which we would like to explore the potential. Based on the Non Uniform FFT algorithm, it is at the same time simple, efficient and versatile. Keywords Quadrature Non uniform FFT Fast convolution Fast multipole method