Multipole expansions and pseudospectral cardinal functions: A new generalization of the fast Fourier transform. (English) Zbl 0765.65022

The author sketches the basic idea and some applications of the fast multipole method (FMM) for computing of \(\sum_{j=1}^ N a_ j/(x-x_ j)\) [see J. Carrier, L. Greengard and V. Rokhlin, SIAM J. Sci. Stat. Comput. 9, No. 4, 669-689 (1988; Zbl 0656.65004)]. The FMM succeeds where the fast Fourier transform fails. The FMM can be used to evaluate Fourier or Chebyshev series on an irregular grid and to expansions of sinc functions, spherical harmonics, Legendre polynomials or Hermite functions.
Reviewer: M.Tasche (Rostock)


65D20 Computation of special functions and constants, construction of tables
65T40 Numerical methods for trigonometric approximation and interpolation


Zbl 0656.65004
Full Text: DOI


[1] Boyd, J. P., Chebyshev & Fourier Spectral Methods (1989), Springer-Verlag: Springer-Verlag New York · Zbl 0681.65079
[2] Gottlieb, D.; Orszag, S. A., Numerical Analysis of Spectral Methods Theory and Applications (1977), SIAM: SIAM Philadelphia · Zbl 0412.65058
[3] Gottlieb, D.; Hussaini, M. Y.; Orszag, S. A., (Voigt, R. G.; Gottlieb, D.; Hussaini, M. Y., Spectral Methodsfor Partial Differential Equations (1984), SIAM: SIAM Philadelphia), 1
[4] Canuto, C.; Hussaini, M. Y.; Quarteroni, A.; Zang, T. A., Spectral Methods for Fluid Dynamics (1987), Springer-Verlag: Springer-Verlag New York · Zbl 0636.76009
[5] Mercier, B., An Introduction to the Numerical Analysis of Spectral Methods (1989), Springer-Verlag: Springer-Verlag New York
[6] Funaro, D., Polynomial Approximation of Differential Equations (1991), To appear
[7] Bisseling, R. H.; Koslof, R.; Kosof, D., Comput. Phys. Commun., 39, 313 (1986)
[8] Schwartz, C., J. Math. Phys., 26, 411 (1985)
[9] Greengard, L., Comput. Phys., 4, 142 (1990)
[10] Greengard, L., The Rapid Evaluation of Potential Fields in Particle Systems (1988), MIT Press: MIT Press Cambridge, MA · Zbl 0661.70006
[11] Orszag, S. A., (Rota, G. C., Science and Computers (1986), Academic Press: Academic Press New York), 23
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.