AM  Vol.5 No.3 , February 2014
Non-Uniform FFT and Its Applications in Particle Simulations
ABSTRACT

Ewald summation method, based on Non-Uniform FFTs (ENUF) to compute the electrostatic interactions and forces, is implemented in two different particle simulation schemes to model molecular and soft matter, in classical all-atom Molecular Dynamics and in Dissipative Particle Dynamics for coarse-grained particles. The method combines the traditional Ewald method with a non-uniform fast Fourier transform library (NFFT), making it highly efficient. It scales linearly with the number of particles as , while being both robust and accurate. It conserves both energy and the momentum to float point accuracy. As demonstrated here, it is straight- forward to implement the method in existing computer simulation codes to treat the electrostatic interactions either between point-charges or charge distributions. It should be an attractive alternative to mesh-based Ewald methods.


Cite this paper
Y. Wang, F. Hedman, M. Porcu, F. Mocci and A. Laaksonen, "Non-Uniform FFT and Its Applications in Particle Simulations," Applied Mathematics, Vol. 5 No. 3, 2014, pp. 520-541. doi: 10.4236/am.2014.53051.
References
[1]   M. P. Allen and D. J. Tildesley, “Computer Simulation of Liquids,” Oxford University Press, New York, 1989.

[2]   J. M. Haile, “Molecular Dynamics Simulation: Elementary Methods,” John Wiley & Sons, New York, 1992.

[3]   D. Frenkel and B. Smit, “Understanding Molecular Simulation: From Algorithms to Applications,” Academic Press, Inc., Orlando, 1996.

[4]   D. M. York, T. A. Darden and L. G. Pedersen, “The Effect of Long-Range Electrostatic Interactions in Simulations of Macromolecular Crystals: A Comparison of the Ewald and Truncated List Methods,” Journal of Chemical Physics, Vol. 99, No. 10, 1993, p. 8345. http://dx.doi.org/10.1063/1.465608

[5]   M. Bergdorf, C. Peter and P. H. Hünenberger, “Influence of Cut-off Truncation and Artificial Periodicity of Electrostatic Interactions in Molecular Simulations of Solvated Ions: A Continuum Electrostatics Study,” Journal of Chemical Physics, Vol. 119, No. 17, 2003, p. 9129.
http://dx.doi.org/10.1063/1.1614202

[6]   C. Anézo, A. H. de Vries, H. D. Holtje, D. P. Tieleman and S. J. Marrink, “Methodological Issues in Lipid Bilayer Simulations,” Journal of Physical Chemistry B, Vol. 107, No. 35, 2003, pp. 9424-9433. http://dx.doi.org/10.1021/jp0348981

[7]   M. Patra, M. Karttunen, M. T. Hyvonen, E. Falck, P. Lindqvist and I. Vattulainen, “Molecular Dynamics Simulations of Lipid Bilayers: Major Artifacts Due to Truncating Electrostatic Interactions,” Biophysical Journal, Vol. 84, No. 6, 2003, pp. 36363645. http://dx.doi.org/10.1016/S0006-3495(03)75094-2

[8]   P. P. Ewald, “Die Berechnung Optischer und Elektrostatischer Gitterpotentiale,” Annalen der Physik, Vol. 369, No. 3, 1921, pp. 253-287. http://dx.doi.org/10.1002/andp.19213690304

[9]   S. W. de Leeuw, J. W. Perram and E. R. Smith, “Simulation of Electrostatic Systems in Periodic Boundary Conditions, I. Lattice Sums and Dielectric Constants,” Proceedings of the Royal Society London, Series A, Vol. 373, No. 1752, 1980, pp. 27-56. http://dx.doi.org/10.1098/rspa.1980.0135

[10]   D. M. Heyes, “Electrostatic Potentials and Fields in Infinite Point Charge Lattices,” Journal of Chemical Physics, Vol. 74, No. 3, 1981, pp. 1924-1929.

[11]   T. Darden, D. York and L. Pedersen, “Particle Mesh Ewald: An NlogN Method for Ewald Sums in Large Systems,” Journal of Chemical Physics, Vol. 98, No. 12, 1993, pp. 10089-10092.
http://dx.doi.org/10.1063/1.464397

[12]   D. York and W. Yang, “The Fast Fourier Poisson Method for Calculating Ewald Sums,” Journal of Chemical Physics, Vol. 101, No. 4, 1994, pp. 3298-3300. http://dx.doi.org/10.1063/1.467576

[13]   U. Essmann, L. Perera, M. L. Berkowitz, T. Darden, H. Lee and L. G. Pedersen, “A Smooth Particle Mesh Ewald Method,” Journal of Chemical Physics, Vol. 103, No. 19, 1995, pp. 8577-8593.
http://dx.doi.org/10.1063/1.470117

[14]   P. F. Batcho and T. Schlick, “New Splitting Formulations for Lattice Summations,” Journal of Chemical Physics, Vol. 115, No. 18, 2001, p. 8312. http://dx.doi.org/10.1063/1.1412247

[15]   D. R. Wheeler and J. Newman, “A Less Expensive Ewald Lattice Sum,” Chemical Physics Letters, Vol. 366, No. 5-6, 2002, pp. 537-543. http://dx.doi.org/10.1016/S0009-2614(02)01644-5

[16]   Y. Shan, J. L. Klepeis, M. P. Eastwood, R. O. Dror and D. E. Shaw, “Gaussian Split Ewald: A Fast Ewald Mesh Method for Molecular Simulation,” Journal of Chemical Physics, Vol. 122, No. 5, 2005, Article ID: 054101.
http://dx.doi.org/10.1063/1.1839571

[17]   P. J. Steinbach and B. R. Brooks, “New Spherical-Cutoff Methods for Long-Range Forces in Macromolecular Simulation,” Journal of Computational Chemistry, Vol. 15, No. 7, 1994, pp. 667-683. http://dx.doi.org/10.1002/jcc.540150702

[18]   C. L. Brooks III, B. M. Pettitt and M. Karplus, “Structural and Energetic Effects of Truncating Long Ranged Interactions in Ionic and Polar Fluids,” Journal of Chemical Physics, Vol. 83, No. 11, 1985, p. 5897. http://dx.doi.org/10.1063/1.449621

[19]   K. S. Kim, “On Effective Methods to Treat Solvent Effects in Macromolecular Mechanics and Simulations,” Chemical Physics Letters, Vol. 156, No. 2-3, 1989, pp. 261-268.
http://dx.doi.org/10.1016/S0009-2614(89)87131-3

[20]   L. Greengard and V. Rokhlin, “A Fast Algorithm for Particle Simulations,” Journal of Computational Physics, Vol. 73, No. 2, 1987, pp. 325-348. http://dx.doi.org/10.1016/0021-9991(87)90140-9

[21]   J. E. Barnes and P. Hut, “A Hierarchical (NlogN) Force-Calculation Algorithm,” Nature, Vol. 324, 1986, pp. 446-449.
http://dx.doi.org/10.1038/324446a0

[22]   J. Pérez-Jordá and W. Yang, “A Simple O(NlogN) Algorithm for the Rapid Evaluation of Particle-Particle Interactions,” Chemical Physics Letters, Vol. 247, No. 4-6, 1995, pp. 484-490.

[23]   Z. H. Duan and R. Krasny, “An Adaptive Treecode for Computing Nonbonded Potential Energy in Classical Molecular Systems,” Journal of Computational Chemistry, Vol. 22, No. 2, 2001, pp. 184-195.
http://dx.doi.org/10.1002/1096-987X(20010130)22:2<184::AID-JCC6>3.0.CO;2-7

[24]   I. Tsukerman, “Efficient Computation of Long-Range Electromagnetic Interactions without Fourier Transforms,” IEEE Transactions on Magnetics, Vol. 40, No. 4, 2004, pp. 2158-2160. http://dx.doi.org/10.1109/TMAG.2004.829022

[25]   E. T. Ong, K. M. Lim, K. H. Lee and H. P. Lee, “A Fast Algorithm for Three-Dimensional Potential Fields Calculation: Fast Fourier Transform on Multipoles,” Journal of Computational Physics, Vol. 192, No. 1, 2003, pp. 244-261.
http://dx.doi.org/10.1016/j.jcp.2003.07.004

[26]   C. Sagui and T. Darden, “Multigrid Methods for Classical Molecular Dynamics Simulations of Biomolecules,” Journal of Chemical Physics, Vol. 114, No. 15, 2001, p. 6578.
http://dx.doi.org/10.1063/1.1352646

[27]   R. D. Skeel, I. Tezcan and D. J. Hardy, “Multiple Grid Methods for Classical Molecular Dynamics,” Journal of Computational Chemistry, Vol. 23, No. 6, 2002, pp. 673-684.
http://dx.doi.org/10.1002/jcc.10072

[28]   J. A. Izaguirre, S. S. Hampton and T. Matthey, “Parallel Multigrid Summation for the N-Body Problem,” Journal of Parallel and Distributed Computing, Vol. 65, No. 8, 2005, pp. 949-962.
http://dx.doi.org/10.1016/j.jpdc.2005.03.006

[29]   J. A. Baker and R. O. Watts, “Monte Carlo Studies of the Dielectric Properties of Water-Like Models,” Molecular Physics, Vol. 26, No. 3, 1973, pp. 789-792. http://dx.doi.org/10.1080/00268977300102101

[30]   I. G. Tironi, R. Sperb, P. E. Smith and W. F. van Gunsteren, “A Generalized Reaction Field Method for Molecular Dynamics Simulations,” Journal of Chemical Physics, Vol. 102, No. 13, 1995, p. 5451. http://dx.doi.org/10.1063/1.469273

[31]   T. N. Heinz and P. H. Hünenberger, “Combining the Lattice-Sum and Reaction-Field Approaches for Evaluating Long-Range Electrostatic Interactions in Molecular Simulations,” Journal of Chemical Physics, Vol. 123, No. 3, 2005, Article ID: 034107.
http://dx.doi.org/10.1063/1.1955525

[32]   R. W. Hockney and J. W. Eastwood, “Computer Simulation Using Particles,” McGraw-Hill, New York, 1981.

[33]   B. A. Luty, M. E. Davis, I. G. Tironi and W. F. van Gunsteren, “A Comparison of Particle-Particle, Particle-Mesh and Ewald Methods for Calculating Electrostatic Interactions in Periodic Molecular Systems,” Molecular Simulation, Vol. 14, No. 1, 1994, pp. 11-20.
http://dx.doi.org/10.1080/08927029408022004

[34]   X. Wu and B. R. Brooks, “Isotropic Periodic Sum: A Method for the Calculation of Long-Range Interactions,” Journal of Chemical Physics, Vol. 122, No. 4, 2005, Article ID: 044107.
http://dx.doi.org/10.1063/1.1836733

[35]   T. M. Apostol, “Mathematical Analysis,” Addison-Wesley, Boston, 1979.

[36]   J. W. Perram, H. G. Petersen and S. W. de Leeuw, “An Algorithm for the Simulation of Condensed Matter Which Grows as the 3/2 Power of the Number of Particles,” Molecular Physics, Vol. 65, No. 4, 1988, pp. 875-893.
http://dx.doi.org/10.1080/00268978800101471

[37]   J. Kolafa and J. W. Perram, “Cutoff Errors in the Ewald Summation Formulae for Point Charge Systems,” Molecular Simulation, Vol. 9, No. 5, 1992, pp. 351-368.
http://dx.doi.org/10.1080/08927029208049126

[38]   S. W. de Leeuw, J. W. Perram and E. R. Smith, “Simulation of Electrostatic Systems in Periodic Boundary Conditions. II. Equivalence of Boundary Conditions,” Proceedings of the Royal Society London, Series A, Vol. 373, No. 1752, 1980, pp. 57-66. http://dx.doi.org/10.1098/rspa.1980.0136

[39]   S. W. de Leeuw, J. W. Perram and E. R. Smith, “Simulation of Electrostatic Systems in Periodic Boundary Conditions. III. Further Theory and Applications,” Proceedings of the Royal Society London, Series A, Vol. 388, No. 1794, 1983, pp. 177-193. http://dx.doi.org/10.1098/rspa.1983.0077

[40]   W. H. Press and G. B. Rybicki, “Fast Algorithm for Spectral Analysis of Unevenly Sampled Data,” Astrophysical Journal, Vol. 338, 1989, pp. 277-280. http://dx.doi.org/10.1086/167197

[41]   J. W. Cooley and J. W. Tukey, “An Algorithm for the Machine Calculation of Complex Fourier Series,” Mathematics of Computation, Vol. 19, 1965, pp. 297-301. http://dx.doi.org/10.1090/S0025-5718-1965-0178586-1

[42]   A. Brandt, “Multilevel Computations of Integral Transforms and Particle Interactions with Oscillatory Kernels,” Computer Physics Communications, Vol. 65, No. 1-3, 1991, pp. 24-38.
http://dx.doi.org/10.1016/0010-4655(91)90151-A

[43]   M. Pippig and D. Potts, “Parallel Three-Dimensional Nonequispaced Fast Fourier Transforms and Their Application to Particle Simulation,” SIAM Journal on Scientific Computing, Vol. 35, No. 4, 2013, pp. 411-437. http://dx.doi.org/10.1137/120888478

[44]   O. Ayala and L. P. Wang, “Parallel Implementation and Scalability Analysis of 3D Fast Fourier Transform Using 2D Domain Decomposition,” Parallel Computing, Vol. 39, No. 1, 2013, pp. 58-77. http://dx.doi.org/10.1016/j.parco.2012.12.002

[45]   Q. Liu and N. Nguyen, “An Accurate Algorithm for Nonuniform Fast Fourier Transforms (NUFFT’s),” IEEE Microwave and Guided Wave Letters, Vol. 8, No. 1, 1998, pp. 18-20.
http://dx.doi.org/10.1109/75.650975

[46]   G. Steidl, “A Note on Fast Fourier Transforms for Nonequispaced Grids,” Advances in Computational Mathematics, Vol. 9, No. 3-4, 1998, pp. 337-352. http://dx.doi.org/10.1023/A:1018901926283

[47]   J. A. Fessler and B. P. Sutton, “Nonuniform Fast Fourier Transforms Using Min-Max Interpolation,” IEEE Transactions on Signal Processing, Vol. 51, No. 2, 2003, pp. 560-574.
http://dx.doi.org/10.1109/TSP.2002.807005

[48]   C. Anderson and M. D. Dahleh, “Rapid Computation of the Discrete Fourier Transform,” SIAM Journal on Scientific Computing, Vol. 17, No. 4, 1996, pp. 913-919. http://dx.doi.org/10.1137/0917059

[49]   A. Duijndam and M. Schonewille, “Nonuniform Fast Fourier Transform,” Geophysics, Vol. 64, No. 2, 1999, p. 539.
http://dx.doi.org/10.1190/1.1444560

[50]   J. P. Boyd, “A Fast Algorithm for Chebyshev, Fourier, and Sinc Interpolation onto an Irregular Grid,” Journal of Computational Physics, Vol. 103, No. 2, 1992, pp. 243-257.
http://dx.doi.org/10.1016/0021-9991(92)90399-J

[51]   A. F. Ware, “Fast Approximate Fourier Transforms for Irregularly Spaced Data,” SIAM Review, Vol. 40, No. 4, 1998, pp. 838-856. http://dx.doi.org/10.1137/S003614459731533X

[52]   A. Nieslony and G. Steidl, “Approximate Factorizations of Fourier Matrices with Nonequispaced Knots,” Linear Algebra and its Applications, Vol. 366, 2003, pp. 337-351.
http://dx.doi.org/10.1016/S0024-3795(02)00496-2

[53]   J. J. Benedetto and P. J. Ferreira, “Modern Sampling Theory: Mathematics and Applications,” Springer, Berlin, 2001.
http://dx.doi.org/10.1007/978-1-4612-0143-4

[54]   S. Kunis and D. Potts, “NFFT3.2.3,” Institute of Mathematics, University of Lübeck, D-23560 Lübeck, 2013.
http://www.math.uni-luebeck.de/potts/nfft/

[55]   F. Hedman and A. Laaksonen, “A Data-Parallel Molecular Dynamics Method for Liquids with Coulombic Interactions,” Molecular Simulation, Vol. 14, No. 4-5, 1995, pp. 235-244.
http://dx.doi.org/10.1080/08927029508022020

[56]   F. Hedman, “Algorithms for Molecular Dynamics Simulations,” Ph.D. Thesis, Stockholm University, Stockholm, 2006.
http://www.diva-portal.org/smash/record.jsf?searchId=1&pid=diva2:178477

[57]   F. Hedman and A. Laaksonen, “Ewald Summation Based on Nonuniform Fast Fourier Transform,” Chemical Physics Letters, Vol. 425, No. 1-3, 2006, pp. 142-147.
http://dx.doi.org/10.1016/j.cplett.2006.04.106

[58]   M. Frigo and S. G. Johnson, “FFTW-The Design and Implementation of FFTW3,” Proceedings of the IEEE, Vol. 93, No. 2, 2005, pp. 216-231. http://dx.doi.org/10.1109/JPROC.2004.840301

[59]   A. P. Lyubartsev and A. Laaksonen, “M.DynaMix—A Scalable Portable Parallel MD Simulation Package for Arbitrary Molecular Mixtures,” Computer Physics Communications, Vol. 128, No. 3, 2000, pp. 565-589.
http://dx.doi.org/10.1016/S0010-4655(99)00529-9

[60]   J. P. Ryckaert, G. Ciccotti and H. J. C. Berendsen, “Numerical Integration of the Cartesian Equations of Motion of a System with Constraints: Molecular Dynamics of n-Alkanes,” Journal of Computational Physics, Vol. 23, No. 3, 1977, pp. 327-341.
http://dx.doi.org/10.1016/0021-9991(77)90098-5

[61]   M. Tuckerman, B. J. Berne and G. J. Martyna, “Reversible Multiple Time Scale Molecular Dynamics,” Journal of Chemical Physics, Vol. 97, 1992, pp. 1990-2001.

[62]   http://www.yolinux.com/TUTORIALS/LinuxTutorialMixingFortranAndC.html

[63]   A. P. Lyubartsev, M. DynaMix User Manual. http://www.fos.su.se/sasha/md_prog.html

[64]   P. J. Hoogerbrugge and V. A. Koelman, “Simulating Microscopic Hydrodynamic Phenomena with Dissipative Particle Dynamics,” Europhysics Letters, Vol. 19, No. 3, 1992, p. 155.
http://dx.doi.org/10.1209/0295-5075/19/3/001

[65]   V. A. Koelman and P. J. Hoogerbrugge, “Dynamic Simulations of Hard-Sphere Suspensions under Steady Shear,” Europhysics Letters, Vol. 21, No. 3, 1993, p. 363. http://dx.doi.org/10.1209/0295-5075/21/3/018

[66]   Z. Y. Lu and Y. L. Wang, “An Introduction to Dissipative Particle Dynamics,” In: L. Monticelli and E. Salonen, Eds., Methods in Molecular Biology: Biomolecular Simulations, Humana Press, New York, 2013, pp. 617-633.
http://link.springer.com/protocol/10.1007/978-1-62703-017-5_24

[67]   P. Espanol and P. Warren, “Statistical Mechanics of Dissipative Particle Dynamics,” Europhysics Letters, Vol. 30, No. 4, 1995, p. 191. http://dx.doi.org/10.1209/0295-5075/30/4/001

[68]   R. D. Groot and P. B. Warren, “Dissipative Particle Dynamics: Bridging the Gap between Atomistic and Mesoscopic Simulation,” Journal of Chemical Physics, Vol. 107, No. 11, 1997, p. 4423. http://dx.doi.org/10.1063/1.474784

[69]   R. D. Groot, “Electrostatic Interactions in Dissipative Particle Dynamics-Simulation of Polyelectrolytes and Anionic Surfactants,” Journal of Chemical Physics, Vol. 118, No. 24, 2003, p. 11265. http://dx.doi.org/10.1063/1.1574800

[70]   M. González-Melchor, E. Mayoral, M. E. Velázquez and J. Alejandre, “Electrostatic Interactions in Dissipative Particle Dynamics Using the Ewald Sums,” Journal of Chemical Physics, Vol. 125, No. 22, 2006, p. 224107.
http://dx.doi.org/10.1063/1.2400223

[71]   Y. L. Wang, A. Laaksonen and Z. Y. Lu, “Implementation of Non-Uniform FFT Based Ewald Summation in Dissipative Particle Dynamics Method,” Journal of Computational Physics, Vol. 235, 2013, pp. 666-682.
http://dx.doi.org/10.1016/j.jcp.2012.09.023

[72]   Y. L. Wang, “Electrostatic Interactions in Coarse-Grained Simulations: Implementations and Applications,” Ph.D. Thesis, Stockholm University, Stockholm, 2013. http://www.diva-portal.org/smash/record.jsf?pid=diva2:641063

[73]   A. AlSunaidi, W. K. den Otter and J. H. R. Clarke, “Liquid-Crystalline Ordering in Rod-Coil Diblock Copolymers Studied by Mesoscale Simulations,” Philosophical Transactions of the Royal Society London A, Vol. 362, No. 1821, 2004, pp. 1773-1781. http://dx.doi.org/10.1098/rsta.2004.1414

[74]   Y. L. Wang, Z. Y. Lu and A. Laaksonen, “Specific Binding Structures of Dendrimers on Lipid Bilayer Membranes,” Physical Chemistry Chemical Physics, Vol. 14, No. 23, 2012, pp. 8348-8359. http://dx.doi.org/10.1039/c2cp40700k

 
 
Top