A new version of the fast multipole method for screened Coulomb interactions in three dimensions. (English) Zbl 1143.78372
Summary: We present a new version of the fast multipole method (FMM) for screened Coulomb interactions in three dimensions. Existing schemes can compute such interactions in \(O(N)\) time, where \(N\) denotes the number of particles. The constant implicit in the \(O(N)\) notation, however, is dominated by the expense of translating far-field spherical harmonic expansions to local ones. For each box in the FMM data structure, this requires \(189p^{4}\) operations per box, where \(p\) is the order of the expansions used. The new formulation relies on an expansion in evanescent plane waves, with which the amount of work can be reduced to \(40p^{2}+6p^{3}\) operations per box.
MSC:
| 78M99 | Basic methods for problems in optics and electromagnetic theory |
| 65B10 | Numerical summation of series |
| 65N99 | Numerical methods for partial differential equations, boundary value problems |
References:
| [1] | Abramowitz, M.; Stegun, I., Handbook of Mathematical Functions (1965) |
| [2] | Biedenharn, L. C.; Louck, J. D., Angular Momentum in Quantum Physics: Theory and Application (1981), Addison-Wesley: Addison-Wesley Reading · Zbl 0474.00023 |
| [3] | Boschtisch, A. H.; Fenley, M. O.; Olson, W. K., A fast adaptive multipole algorithm for calculating screened Coulomb (Yukawa) interactions, J. Comput. Phys., 151, 212 (1999) · Zbl 1017.92500 |
| [4] | Cheng, H.; Greengard, L.; Rokhlin, V., A fast adaptive fast multipole algorithm in three dimensions, J. Comput. Phys., 155, 468 (1999) · Zbl 0937.65126 |
| [5] | Danos, X.; Maximon, X., Multipole matrix elements of the translation operator, J. Math. Phys., 6, 766 (1965) |
| [6] | Epton, M. A.; Dembart, B., Multipole translation theory for three-dimensional Laplace and Helmholtz equations, SIAM J. Sci. Comput., 16, 865 (1995) · Zbl 0852.31006 |
| [7] | Greengard, L., The Rapid Evaluation of Potential Fields in Particle Systems (1988), MIT Press: MIT Press Cambridge · Zbl 0661.70006 |
| [8] | Greengard, L.; Huang, J.; Rokhlin, V.; Wandzura, S., Accelerating fast multipole methods for low frequency scattering, IEEE Comp. Sci. Eng., 5, 32 (1998) |
| [9] | L. Greengard, and, V. Rokhlin, Rapid evaluation of potential fields in three dimensions, in, Vortex Methods, edited by, C. Anderson and C. Greengard, Lecture Notes in Mathematics, Springer-Verlag, Berlin/New York, 1988, Vol, 1360.; L. Greengard, and, V. Rokhlin, Rapid evaluation of potential fields in three dimensions, in, Vortex Methods, edited by, C. Anderson and C. Greengard, Lecture Notes in Mathematics, Springer-Verlag, Berlin/New York, 1988, Vol, 1360. · Zbl 0661.70006 |
| [10] | Greengard, L.; Rokhlin, V., A new version of the fast multipole method for the Laplace equation in three dimensions, Acta Numer., 6, 229 (1997) · Zbl 0889.65115 |
| [11] | Hobson, E. W., The Theory of Spherical and Ellipsoidal Harmonics (1955), Chelsea: Chelsea New York · Zbl 0004.21001 |
| [12] | Jackson, J. D., Classical Electrodynamics (1975), Wiley: Wiley New York · Zbl 0997.78500 |
| [13] | Juffer, A. H.; Botta, E. F.F.; Keulen, B. A.M. V.; Ploeg, A. V.D.; Berendsen, H. J.C., The electric potential of a macromolecule in a solvent: A fundamental approach, J. Comput. Phys., 97, 144 (1991) · Zbl 0743.65094 |
| [14] | Liang, J.; Subramaniam, S., Computation of molecular electrostatics with boundary element methods, Biophys. J., 73, 1830 (1997) |
| [15] | Morse, P. M.; Feshbach, H., Methods of Theoretical Physics (1953), McGraw-Hill: McGraw-Hill New York · Zbl 0051.40603 |
| [16] | Rokhlin, V., Diagonal forms of translation operators for the Helmholtz equation in three dimensions, Appl. Comput. Harmonic Anal., 1, 82 (1993) · Zbl 0795.35021 |
| [17] | Russell, W. B.; Seville, D. A.; Schowalter, W. R., Colloidal Dispersions (1991) · Zbl 0789.76003 |
| [18] | Song, J. M.; Chew, W. C., Multilevel fast multipole algorithm for solving combined field integral equations of electromagnetic scattering, Microwave Opt. Technol. Lett., 10, 14 (1994) |
| [19] | Yarvin, N.; Rokhlin, V., Generalized Gaussian quadratures and singular value decompositions of integral operators, SIAM J. Sci. Comput., 20, 699 (1999) · Zbl 0932.65020 |
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.
