A rigorous comparison of the Ewald method and the fast multipole method in two dimensions. (English) Zbl 0888.65130
Summary: The most efficient and proper standard method for simulating charged or dipolar systems is the Ewald method, which asymptotically scales as \(N^{3/2}\), where \(N\) is the number of charges. However, recently the “fast multipole method” (FMM) which scales linearly with \(N\) has been developed. The break-even of the two methods (that is, the value of \(N\) below which Ewald is faster and above which FMM is faster) is very sensitive to the way the methods are optimized and implemented and to the required simulation accuracy.
In this paper, we use theoretical estimates and simulation results for the accuracies to carefully compare the two methods with respect to speed. We have developed and implemented highly efficient algorithms for both methods for a serial computer (a SPARCstation ELC) as well as a parallel computer (a T800 transputer based MEIKO computer). Breakevens in the range between \(N= 10000\) and \(N=30000\) were found for reasonable values of the average accuracies found in our simulations. Furthermore, we illustrate how huge but rare single charge pair errors in the FMM inflate the error for some of the charges.
In this paper, we use theoretical estimates and simulation results for the accuracies to carefully compare the two methods with respect to speed. We have developed and implemented highly efficient algorithms for both methods for a serial computer (a SPARCstation ELC) as well as a parallel computer (a T800 transputer based MEIKO computer). Breakevens in the range between \(N= 10000\) and \(N=30000\) were found for reasonable values of the average accuracies found in our simulations. Furthermore, we illustrate how huge but rare single charge pair errors in the FMM inflate the error for some of the charges.
MSC:
| 65Z05 | Applications to the sciences |
| 65C05 | Monte Carlo methods |
| 35Q60 | PDEs in connection with optics and electromagnetic theory |
| 35Q72 | Other PDE from mechanics (MSC2000) |
| 81V55 | Molecular physics |
| 78A35 | Motion of charged particles |
| 82B80 | Numerical methods in equilibrium statistical mechanics (MSC2010) |
Keywords:
molecular dynamics; Monte Carlo simulation; fast multipole method; charged or dipolar systems; Ewald method; simulation; algorithmsReferences:
| [1] | Kolafa, J.; Perram, J. W., Cutoff errors in the Ewald summation formulae for point charge systems, Molec. Simul., 9, 351-368 (1992) |
| [2] | Perram, J. W.; de Leeuw, S. W., Statistical mechanics of two-dimensional Coulomb systems. I. Lattice sums and simulation methodology, Physica A, 109, 237-250 (1981) |
| [3] | Allen, M. P.; Tildesley, D. J., Computer Simulations of Liquids (1987), Clarendon Press: Clarendon Press Oxford · Zbl 0703.68099 |
| [4] | Greengard, L.; Rokhlin, V., A fast algorithm for particle simulations, J. Comput. Phys., 73, 325-348 (1987) · Zbl 0629.65005 |
| [5] | Christiansen, D.; Petersen, H. G.; Perram, J. W., On the fast multipole method for computing the energy of periodic assemblies of charged and dipolar particles, J. Comput. Phys., 107, 403-405 (1993) · Zbl 0785.65002 |
| [6] | de Leeuw, S. W.; Perram, J. W.; Smith, E. R., Simulation of electrostatic systems in periodic boundary conditions. I. Lattice sums and dielectric constants, (Proc. R. Soc. A, 373 (1980)), 27-56 |
| [7] | Perram, J. W.; Petersen, H. G.; de Leeuw, S. W., An algorithm for the simulation of condensed matter which grows as the ((N^{32}\) power of the number of particles, Molec. Phys., 65, 875-893 (1988) |
| [8] | Hockney, R. W.; Eastwood, J. W., Computer simulation using particles (1981), McGraw-Hill: McGraw-Hill New York · Zbl 0662.76002 |
| [9] | Schmidt, K. E.; Lee, M. A., Implementing the fast multipole method in three dimensions, J. Stat. Phys., 63, 1223-1235 (1991) |
| [10] | D. Sølvason, H.G. Petersen, J.W. Perram and E.R. Smith, Error estimates for the fast multipole method. I. The two-dimensional case, Proc. Roy. Soc. London, accepted.; D. Sølvason, H.G. Petersen, J.W. Perram and E.R. Smith, Error estimates for the fast multipole method. I. The two-dimensional case, Proc. Roy. Soc. London, accepted. · Zbl 0831.65135 |
| [11] | E.R. Smith, Internal notes.; E.R. Smith, Internal notes. |
| [12] | H.G. Petersen, in preparation.; H.G. Petersen, in preparation. |
| [13] | Ding, H.-Q.; Karasawa, N.; Goddard, W. A., Atomic level simulations on a million particles: The cell multipole method for Coulomb and London nonbond interactions, J. Chem. Phys., 97, 4309-4315 (1992) |
| [14] | Ding, H.-Q.; Karasawa, N.; Goddard, W. A., The reduced cell multipole method for Coulomb interactions in periodic systems with million-atom unit cells, Chem. Phys. Lett., 196, 6-10 (1992) |
| [15] | Darden, T.; York, D.; Pedersen, L., Particle mesh Ewald: An \(N log (N)\) method for Ewald sums in large systems, J. Chem. Phys., 98, 10089-10092 (1993) |
| [16] | Petersen, H. G.; Perram, J. W., Molecular dynamics on transputer arrays. I. Algorithm design, programming issues, timing experiments and scaling projections, Molec. Phys., 67, 849-860 (1989) |
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.
