Ewald summation techniques in perspective: A survey. (English) Zbl 0923.65090
Summary: The simulation of large macromolecular systems has been and remains a challenging problem. There is a general presumption that simulation carried in periodic boundary conditions (PBC) are often the most appropriate to suppress boundary effects. To this end, Ewald summation has been employed to handle long ranged interactions in PBC. There has been a great deal of research targeted at improving the efficiency of Ewald summation, an \({\mathcal O}(N^2)\) algorithm in its traditional formulation, where \(N\) is the number of particles in the system. This paper reviews Ewald summation techniques by surveying conventional as well as state of the art efficient methods. Conventional methods, such as tabulation and approximation, are first re-examined along with an \({\mathcal O}(N^{3/2})\) method. Fourier-based approaches which have reduced the complexity to \({\mathcal O}(N\log(N))\) are presented. Multipole expansion techniques, suggested as an alternative to Ewald sums, are reviewed and compared to Fourier methods. The computational efficiency of these new methods facilitates longer, larger and more realistic simulations.
MSC:
| 65Z05 | Applications to the sciences |
| 35Q40 | PDEs in connection with quantum mechanics |
| 81V55 | Molecular physics |
| 65C05 | Monte Carlo methods |
| 35Q72 | Other PDE from mechanics (MSC2000) |
| 92D20 | Protein sequences, DNA sequences |
| 65Y20 | Complexity and performance of numerical algorithms |
Keywords:
Ewald summation; fast multipole algorithm; particle-mesh algorithms; periodic boundary conditions; molecular dynamics; algorithms; enzymes; proteins; DNA strands; membranes; biological systems; large macromolecular systems; computational efficiencyReferences:
| [1] | Abramowitz, M.; Stegun, I., (Handbook of Mathematical Functions, National Bureau of Standards, AMS 55 (1964), US Government: US Government Washington, DC) · Zbl 0171.38503 |
| [2] | Adams, D.; Dubey, G., J. Comp. Phys., 72, 156 (1987) · Zbl 0616.65007 |
| [3] | Allen, M.; Tildesley, D., Computer Simulation of Liquids (1990), Oxford Science: Oxford Science London · Zbl 0703.68099 |
| [4] | Anderson, C. R., SIAM J. Sci. Stat. Comput., 13, 923 (1992) · Zbl 0754.65101 |
| [5] | Bader, J.; Chandler, D., J. Phys. Chem., 96, 6423 (1992) |
| [6] | Belhadj, M.; Alper, H.; Levy, R., Chem. Phys. Lett., 179, 13 (1991) |
| [7] | Berendson, H. J., (van Gunsteren, W. F.; Weiner, P. K., Computer simulation of biomolecular systems 2 (1993), ESCOM Science Publishers: ESCOM Science Publishers Leiden, The Netherlands), 161 |
| [8] | Berman, C.; Greengard, L., J. Math. Phys., 35, 6036 (1994) · Zbl 0819.65013 |
| [9] | Board, J.; Batchelor, R.; Leathrum, J., (Proc. AIAA/ASME Thermophysics and Heat Transfer Conf. (1990)) |
| [10] | Board, J.; Causey, J.; Leathrum, J.; Windemuth, A.; Schulten, K., Chem. Phys. Lett., 198, 89 (1992) |
| [11] | Born, M.; Von Karman, Th., Physik. Z., 13, 297 (1912) · JFM 43.0970.03 |
| [12] | Brooks, B. R.; Bruccoleri, R. E.; Olafson, B. D.; States, D. J.; Swaminathan, S.; Karplus, M., J. Comput. Chem., 4, 187 (1983) |
| [13] | Brush, S.; Sahlin, H.; Teller, E., J. Chem. Phys., 45, 2101 (1966) |
| [14] | Darden, T.; York, D.; Pederson, L., J. Chem. Phys., 98, 10089 (1993) |
| [15] | Darden, T.; Essmann, U.; Lee, H.; Perera, L.; Berkowitz, M.; Pederson, L. G., J. Chem. Phys., 103, 8577 (1995) |
| [16] | Deem, M.; Newsam, J.; Sinha, S., J. Phys. Chem., 94, 8356 (1990) |
| [17] | De Leeuw, S.; Perram, J.; Smith, E., (Proc. Roy. Soc. London A, 373 (1980)), 27 |
| [18] | Ding, H.; Karasawa, N.; Goddard, W. A., J. Chem. Phys., 97, 4309 (1992) |
| [19] | Ding, H.; Karasawa, N.; Goddard, W. A., Chem. Phys. Lett., 196, 6 (1992) |
| [20] | Eastwood, J.; Hockney, R.; Lawrence, D., Comput. Phys. Commun., 19, 215 (1980) |
| [21] | Elliott, W.; Board, J., (Technical Report 94-005 (1994), EE Dept. Duke University), unpublished |
| [22] | Esselink, K., Comput. Phys. Commun., 87, 375 (1995) |
| [23] | Ewald, P., Ann. Phys., 64, 253 (1921) · JFM 48.0566.02 |
| [24] | Farouki, R.; Hamaguchi, S., J. Comp. Phys., 115, 276 (1994) · Zbl 0810.65003 |
| [25] | Fincham, D., Mol. Simulation, 13, 1 (1994) |
| [26] | Greengard, L.; Rokhlin, V., J. Comp. Phys., 73, 325 (1987) · Zbl 0629.65005 |
| [27] | Greengard, L., The Rapid Evaluation of Potential Fields in Particle Systems (1988), MIT Press: MIT Press Cambridge, MA · Zbl 0661.70006 |
| [28] | Hansen, J., Phys. Rev. A, 8, 3096 (1973) |
| [29] | Hautman, J.; Klein, M., Mol. Sim., 75, 379 (1992) |
| [30] | Heyes, D., J. Chem. Phys., 74, 1924 (1980) |
| [31] | Hockney, R.; Eastwood, J., Computer simulation using particles (1981), McGraw-Hill: McGraw-Hill New York · Zbl 0662.76002 |
| [32] | Jackson, J. D., Classical Electrodynamics (1975), Wiley: Wiley New York · Zbl 0114.42903 |
| [33] | Kittel, C., Introduction to Solid State Physics (1971), Wiley: Wiley New York |
| [34] | Kolafa, J.; Perram, J., Mol. Simulation, 9, 351 (1992) |
| [35] | Kutteh, R.; Nicholas, J., Comput. Phys. Commun., 86, 236 (1995) |
| [36] | C. Lambert and J. Board Jr., J. Comp. Phys., submitted.; C. Lambert and J. Board Jr., J. Comp. Phys., submitted. |
| [37] | Luty, B.; Davis, M.; Tironi, I.; van Gunsteren, W., Mol. Simulation, 14, 11 (1994) |
| [38] | Nijboer, B.; De Wette, F., Physica, 23, 309 (1957) · Zbl 0131.46201 |
| [39] | Perram, J.; Petersen, H.; De Leeuw, S., Mol. Phys., 65, 875 (1988) |
| [40] | Rajagopal, G.; Needs, R., J. Comp. Phys., 115, 399 (1994) · Zbl 0843.65086 |
| [41] | Rhee, Y.; Halley, J.; Hautman, J.; Rahman, A., Phys. Rev. B, 40, 36 (1989) |
| [42] | Rycerz, Z.; Jacobs, P., Mol. Simulation, 8, 197 (1992) |
| [43] | Sangester, M.; Dixon, M., Adv. Phys., 25, 247 (1976) |
| [44] | Schmidt, K.; Lee, M., J. Stat. Phys., 63, 1223 (1991) |
| [45] | Schreiber, H.; Steinhauser, O., Biochemistry, 31, 5856 (1992) |
| [46] | Shimada, J.; Kaneko, H.; Takada, T., J. Comp. Chem., 14, 867 (1993) |
| [47] | Shimada, J.; Kaneko, H.; Takada, T., J. Comp. Chem., 15, 28 (1994) |
| [48] | Slattery, W.; Doolen, G.; DeWitt, H., Phys. Rev. A, 21, 2087 (1980) |
| [49] | Solvason, D.; Kolafa, J.; Peterson, J.; Perram, J., Comput. Phys. Commun., 87, 307 (1995) · Zbl 0888.65130 |
| [50] | Smith, W., Information Quarterly for Computer Simulation of Condensed Phases, 21, 37 (1986) |
| [51] | Tosi, M., (Seitz, F.; Turnbull, D., Solid State Physics 16 (1964), Academic Press: Academic Press New York), 107 |
| [52] | Von der Lage, F.; Bethe, H., Phys. Rev., 71, 612 (1947) · Zbl 0033.14303 |
| [53] | York, D.; Yang, W., J. Chem. Phys., 101, 3298 (1994) |
| [54] | York, D.; Wlodawer, A.; Pedersen, L.; Darden, T., (Proc. Natl. Acad. Sci., 91 (1994)), 8715 |
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.
