Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-24T02:55:22.206Z Has data issue: false hasContentIssue false
  • English
  • Français

A new version of the Fast Multipole Method for the Laplace equation in three dimensions

Published online by Cambridge University Press:  07 November 2008

Leslie Greengard  and
Vladimir Rokhlin
Leslie Greengard
Affiliation:
Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA
Vladimir Rokhlin
Affiliation:
Departments of Mathematics and Computer Science, Yale University, New Haven, CT 06520, USA
Get access Rights & Permissions [Opens in a new window]

Abstract

We introduce a new version of the Fast Multipole Method for the evaluation of potential fields in three dimensions. It is based on a new diagonal form for translation operators and yields high accuracy at a reasonable cost.

Type
Research Article
Information
Acta Numerica , Volume 6 , January 1997 , pp. 229 - 269
Copyright
Copyright © Cambridge University Press 1997

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Alpert, B. K. and Rokhlin, V. (1991), ‘A fast algorithm for the evaluation of Legendre expansions’, SIAM J. Sci. Statist. Comput. 12, 158–179.CrossRefGoogle Scholar
Alpert, B. K., Beylkin, G., Coifman, R. and Rokhlin, V. (1993), ‘Wavelet-like bases for the fast solution of second-kind integral equations’, SIAM J. Sci. Statist. Comput. 14, 159–184.Google Scholar
Anderson, C. R. (1986), ‘A method of local corrections for computing the velocity field due to a distribution of vortex blobs’, J. Comput. Phys. 62, 111–123.Google Scholar
Anderson, C. R. (1992), ‘An implementation of the fast multipole method without multipoles’, SIAM J. Sci. Statist. Comput. 13, 923–947.CrossRefGoogle Scholar
Appel, A. W. (1985), ‘An efficient program for many-body simulation’, SIAM J. Sci. Statist. Comput. 6, 85–103.Google Scholar
Barnes, J. and Hut, P. (1986), ‘A hierarchical O(N log N) force-calculation algorithm’, Nature 324, 446–449.CrossRefGoogle Scholar
Berman, L. (1995), ‘Grid-multipole calculations’, SIAM J. Sci. Comput. 16, 1082–1091.Google Scholar
Beylkin, G., Coifman, R. and Rokhlin, V. (1991), ‘Fast wavelet transforms and numerical algorithms I’, Comm. Pure Appl. Math. 44, 141–183.CrossRefGoogle Scholar
Biedenharn, L. C. and Louck, J. D. (1981), Angular Momentum in Quantum Physics: Theory and Application, Addison Wesley, London.Google Scholar
Board, J. A., Causey, J. W., Leathrum, J. F., Windemuth, A. and Schulten, K. (1992), ‘Accelerated molecular dynamics simulation with the parallel fast multipole method’, Chem. Phys. Let. 198, 89–94.CrossRefGoogle Scholar
Bradie, B., Coifman, R. and Grossmann, A. (1993), ‘Fast numerical computations of oscillatory integrals related to acoustic scattering, I’, Appl. Comput. Harm. Anal. 1, 94–99.CrossRefGoogle Scholar
Brandt, A. (1991), ‘Multilevel computations of integral transforms and particle interactions with oscillatory kernels’, Comp. Phys. Comm. 65, 24–38.CrossRefGoogle Scholar
Brandt, A. and Lubrecht, A. A. (1990), ‘Multilevel matrix multiplication and fast solution of integral equations’, J. Comput. Phys. 90, 348–370.Google Scholar
Canning, F. X. (1989), ‘Reducing moment method storage from order N 2 to order N’, Electron. Let. 25, 1274–1275.Google Scholar
Canning, F. X. (1992), ‘Sparse approximation for solving integral equations with oscillatory kernels’, SIAM J. Sci. Statist. Comput. 13, 71–87.Google Scholar
Canning, F. X. (1993), ‘Improved impedance matrix localization method’, IEEE Trans. Antennas and Propagation 41, 658–667.CrossRefGoogle Scholar
Carrier, J., Greengard, L. and Rokhlin, V. (1988), ‘A fast adaptive multipole algorithm for particle simulations’, SIAM J. Sci. Statist. Comput. 9, 669–686.CrossRefGoogle Scholar
Coifman, R. and Meyer, Y. (1991), ‘Remarques sur l'analyse de Fourier à fenêtre’, C. R. Acad. Sci. Paris 312, Serie 1, 259–261.Google Scholar
Coifman, R., Rokhlin, V. and Wandzura, S. (1993), ‘The fast multipole method for the wave equation: a pedestrian prescription’, IEEE Antennas and Propagation Mag. 35, 7–12.CrossRefGoogle Scholar
Coifman, R., Rokhlin, V. and Wandzura, S. (1994), ‘Faster single-stage Multipole Method for the wave equation’, 10th Annual Review of Progress in Applied Computational Electromagnetics, Vol. 1, pp. 19–24, Monterey, CA, Applied Computational Electromagnetics Society.Google Scholar
Dahlquist, G. and Bjork, A. (1974), Numerical Methods Prentice-Hall, Englewood Cliffs, NJ.Google Scholar
Ding, H.-Q., Karasawa, N. and Goddard, W. A. III (1992), ‘Atomic level simulations on a million particles: The Cell Multipole Method for Coulomb and London nonbond interactions, J. Chem. Phys. 97, 4309–4315.CrossRefGoogle Scholar
Elliott, W. D. and Board, J. A. (1996), ‘Fast Fourier Transform accelerated fast multipole algorithm’, SIAM J. Sci. Comput. 17, 398–415.CrossRefGoogle Scholar
Epton, M. A. and Dembart, B. (1995), ‘Multipole translation theory for three-dimensional Laplace and Helmholtz equations’, SIAM J. Sci. Comput. 16, 865–897.Google Scholar
Greenbaum, A., Greengard, L. and McFadden, G. B. (1993), ‘Laplace’s equation and the Dirichlet–Neumann map in multiply connected domains‘, J. Comput. Phys. 105, 267–278.CrossRefGoogle Scholar
Greengard, L. (1988), The Rapid Evaluation of Potential Fields in Particle Systems, MIT Press, Cambridge, MA.Google Scholar
Greengard, L. (1990), ’The numerical solution of the N-body problem’, Computers in Physics 4, 142–152.Google Scholar
Greengard, L. (1994), ‘Fast algorithms for classical physics’, Science 265, 909–914.CrossRefGoogle ScholarPubMed
Greengard, L. and Lee, J.-Y. (1996), ‘A direct adaptive Poisson solver of arbitrary order accuracy’, J. Comput. Phys. 125, 415–424.Google Scholar
Greengard, L. and Moura, M. (1994), ‘On the numerical evaluation of electrostatic fields in composite materials’, in Acta Numerica, Vol. 3, Cambridge University Press, pp. 379–410.Google Scholar
Greengard, L. and Rokhlin, V. (1987), ‘A fast algorithm for particle simulations’, J. Comput. Phys. 73, 325–348.CrossRefGoogle Scholar
Greengard, L. and Rokhlin, V. (1988 a), ‘Rapid evaluation of potential fields in three dimensions’, in Vortex Methods, Anderson, C. and Greengard, C. (eds.), Lecture Notes in Mathematics, vol. 1360, Springer, 121–141.Google Scholar
Greengard, L. and Rokhlin, V. (1988 b), ‘On the efficient implementation of the fast multipole algorithm’, Department of Computer Science Research Report 602, Yale University.Google Scholar
Greengard, L. and Rokhlin, V. (1989), ‘On the evaluation of electrostatic interactions in molecular modeling’, Chemica Scripta 29A, 139–144.Google Scholar
Greengard, L. and Strain, J. (1991), ‘The fast Gauss transform’, SIAM J. Sci. Statist. Comput. 12, 79–94.Google Scholar
Greengard, L., Kropinski, M. C. and Mayo, A. (1996), ‘Integral equation methods for Stokes flow and isotropic elasticity’, J. Comput. Phys. 125, 403–414.CrossRefGoogle Scholar
Gu, M. and Eisenstat, S. C. (1992), ‘A divide-and-conquer algorithm for the symmetric tridiagonal eigenproblem’, Department of Computer Science Research Report 932, Yale University.Google Scholar
Hackbusch, W. and Nowak, Z. P. (1989), ‘On the fast matrix multiplication in the boundary element method by panel clustering’, Numer. Math. 54, 463–491.Google Scholar
Hobson, E. W. (1955), Spherical and Ellipsoidal Harmonics, Dover, New York.Google Scholar
Hockney, R. W. and Eastwood, J. W. (1981), Computer Simulation Using Particles, McGraw-Hill, New York.Google Scholar
Hrycak, T. and Rokhlin, V. (1995), ‘An improved fast multipole algorithm for potential fields’, Department of Computer Science Research Report 1089, Yale University.CrossRefGoogle Scholar
Jackson, J. D. (1975), Classical Electrodynamics, Wiley, New York.Google Scholar
Kellogg, O. D. (1953), Foundations of Potential Theory, Dover, New York.Google Scholar
Morse, P. M. and Feshbach, H. (1953), Methods of Theoretical Physics, McGraw-Hill, New York.Google Scholar
Nabors, K. and White, J. (1991), ‘FastCap: a multipole accelerated 3-D capacitance extraction program’, IEEE Trans. Computer-Aided Design 10, 1447–1459.Google Scholar
Nabors, K. and White, J. (1992), ‘Multipole-accelerated capacitance extraction algorithms for 3-D structures with multiple dielectrics’, IEEE Trans. Circuits and Systems 39, 946–954.Google Scholar
Nabors, K., Korsmeyer, F. T., Leighton, F. T. and White, J. (1994), ‘Preconditioned, adaptive, multipole-accelerated iterative methods for three-dimensional first-kind integral equations of potential theory’, SIAM J. Sci. Statist. Comput. 15, 714–735.CrossRefGoogle Scholar
Odlyzko, A. M. and A. Schönhage (1988), ‘Fast algorithms for multiple evaluations of the Riemann zeta function’, Trans. Amer. Math. Soc. 309, 797–809.CrossRefGoogle Scholar
Petersen, H. G., Smith, E. R. and Soelvason, D. (1995), ‘Error estimates for the fast multipole method. II. The three-dimensional case’, Proc. R. Soc. London, Series A 448, 401–418.Google Scholar
Rokhlin, V. (1985), ‘Rapid solution of integral equations of classical potential theory’, J. Comput. Phys. 60, 187–207.CrossRefGoogle Scholar
Rokhlin, V. (1988), ‘A fast algorithm for the discrete Laplace transformation’, J. Complexity 4, 12–32.CrossRefGoogle Scholar
Rokhlin, V. (1990 a), ‘End-point corrected trapezoidal quadrature rules for singular functions’, Computers Math. Applic. 20, 51–62.Google Scholar
Rokhlin, V. (1990 b), ‘Rapid solution of integral equations of scattering theory in two dimensions’, J. Comput. Phys. 86, 414–439.CrossRefGoogle Scholar
Rokhlin, V. (1993), ‘Diagonal forms of translation operators for the Helmholtz equation in three dimensions’, Appl. Comput. Harm. Anal. 1, 82–93.CrossRefGoogle Scholar
Rokhlin, V. (1995), ‘Sparse diagonal forms of translation operators for the Helmholtz equation in two dimensions, Department of Computer Science Research Report 1095, Yale University.Google Scholar
Song, J. M. and Chew, W. C. (1995), ‘Multilevel fast multipole algorithm for solving combined field integral equations of electromagnetic scattering’, Microwave and Opt. Technol. Letters 10 14–19.Google Scholar
Strain, J. (1991), ‘The Fast Gauss Transform with variable scales’, SIAM J. Sci. Statist. Comput. 12, 1131–1139.CrossRefGoogle Scholar
Strain, J. (1992), ‘The Fast Laplace Transform based on Laguerre functions’, Math. Comp. 58, 275–283.CrossRefGoogle Scholar
Van Dommelen, L. and Rundensteiner, E. A. (1989), ‘Fast, adaptive summation of point forces in the two-dimensional Poisson equation’, J. Comput. Phys. 83, 126–147.CrossRefGoogle Scholar
Wallace, P. R. (1984), Mathematical Analysis of Physical Problems, Dover, New York.Google Scholar
Wagner, R. L. and Chew, W. C. (1994), ‘A ray-propagation fast multipole algorithm’, Microwave and Opt. Technol. Letters 7 348–351.CrossRefGoogle Scholar
Wagner, R. L. and Chew, W. C. (1995), ‘A study of wavelets for the solution of electromagnetic integral equations’, IEEE Antennas Propag. 43 802–810.Google Scholar
Wang, H. Y. and LeSar, R. (1995), ‘An efficient fast-multipole algorithm based on an expansion in the solid harmonics’, J. Chem. Phys. 104, 4173–4179.Google Scholar
Watson, G. N. (1944), A Treatise on the Theory of Bessel Functions, Cambridge University Press.Google Scholar
Yarvin, N. and Rokhlin, V. (1996), ‘Generalized Gaussian quadratures and singular value decompositions of integral operators’, Department of Computer Science Research Report 1109, Yale University.Google Scholar