Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



A fast algorithm for Brownian dynamics simulation with hydrodynamic interactions

Authors: Shidong Jiang, Zhi Liang and Jingfang Huang
Journal: Math. Comp. 82 (2013), 1631-1645
MSC (2010): Primary 76M35, 65Z05, 65C60, 65F60
Published electronically: February 27, 2013
MathSciNet review: 3042579
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: One of the critical steps in Brownian dynamics simulation with hydrodynamic interactions is to generate a normally distributed random vector whose covariance is determined by the Rotne-Prager-Yamakawa tensor. The standard algorithm for generating such a random vector calls for the Cholesky decomposition of a $ 3N\times 3N$ matrix and thus requires $ O(N^3)$ operations for $ N$ particles, which is prohibitively slow for large scale simulations. In this paper, we present a fast algorithm for generating such random vectors. Our algorithm combines the Chebyshev spectral approximation for the square root of a positive definite matrix and kernel independent fast multipole method. The overall complexity of the algorithm is $ O(\sqrt {\kappa }N)$ with $ \kappa $ the condition number of the matrix and $ N$ the size of the particle system. Numerical experiments show that the algorithm can be applied to various particle configurations with essentially $ O(N)$ operations since $ \kappa $ is usually small and independent of $ N$. Thus, our fast algorithm will be useful for the study of diffusion limited reactions, polymer dynamics, protein folding, and particle coagulation as it enables large scale Brownian dynamics simulations. Finally, the algorithm can be extended to speed up the computation involving the matrix square root for many other matrices, which has potential applications on areas such as statistical analysis with certain spatial correlations and model reduction in dynamic control theory.

References [Enhancements On Off] (What's this?)

  • 1. G. K. Batchelor, Brownian Diffusion of Particles with Hydrodynamic Interaction. J. Fluid Mech. 74 (1976), 1-29. MR 0406082 (53:9874)
  • 2. S. H. Cheng, N. J. Higham, C. S. Kenney, and A. J. Laub, Approximating the Logarithm of a Matrix to Specified Accuracy. SIAM J. Matrix Anal. Appl. 22 (2001), 1112-1125. MR 1825853 (2002a:65069)
  • 3. G. Dahlquist and A. Bjorck, Numerical Methods, Prentice Hall, Englewood Cliffs (1974). MR 0368379 (51:4620)
  • 4. M. H. DeGroot and M. J. Schervish, Probability and Statistics, third edition, Addison Wesley, 2002.
  • 5. J. M. Deutch and I. Oppenheim, Molecular Theory of Brownian Motion for Several Particles. J. Chem. Phys. 54 (1971), 3547-3554.
  • 6. D. L. Ermak and J. A. McCammon, Brownian Dynamics with Hydrodynamic Interactions. J. Chem. Phys. 69 (1978), 1352-1360.
  • 7. B. U. Felderhof and J. M. Deutch, Frictional Properties of Dilute Polymer Solutions I. Rotational Friction Coefficient. J. Chem. Phys. 62 (1975), 2391-2397.
  • 8. M. Fixman, Implicit Algorithm for Brownian Dynamics of Polymers. Macromolecules 19 (1986), 1195-1204.
  • 9. W. Fong and E. Darve, The Black-Box Fast Multipole Method. J. Comp. Phys. 228 (2009), 8712-8725. MR 2558773 (2010m:65009)
  • 10. B. Fornberg, A Practical Guide to Pseudospectral Methods, Cambridge University Press, 1998. MR 1386891 (97g:65001)
  • 11. H. L. Friedman, A Hydrodynamic Effect in the Rates of Diffusion Controlled Reactions. J. Chem. Phys. 70 (1966), 3931-3933.
  • 12. P. G. de Gennes, Passive Entry of a DNA Molecule into a Small Pore. Proc. Natl. Acad. Sci. USA 96 (1999), 7262-7264.
  • 13. T. Geyer and U. Winter, An $ O(N^2)$ Approximation for Hydrodynamic Interactions in Brownian Dynamics Simulations. J. Chem. Phys. 130 (2009), 114905.
  • 14. Z. Gimbutas and V. Rokhlin, A Generalized Fast Multipole Method for Nonoscillatory Kernels. SIAM J. Sci. Comput. 24 (2003), 796-817. MR 1950512 (2004a:65176)
  • 15. G. H. Golub and C. F. Van Loan, Matrix Computations, The Johns Hopkins University Press (1996). MR 1417720 (97g:65006)
  • 16. L. Greengard, D. Gueyffier, P.G. Martinsson and V. Rokhlin, Fast Direct Solvers for Integral Equations in Complex Three-Dimensional Domains. Acta Numerica 18 (2009), 243-275. MR 2506042 (2010e:65252)
  • 17. L. Greengard and V. Rokhlin, A Fast Algorithm for Particle Simulations. J. Comp. Phys. 73 (1987), 325-348. MR 918448 (88k:82007)
  • 18. L. Greengard and V. Rokhlin, A New Version of the Fast Multipole Method for the Laplace Equation in Three Dimensions. Acta Numerica 6 (1997), 229-269. MR 1489257 (99c:65012)
  • 19. B. B. Haab and R. A. Mathies, Single-Molecule Detection of DNA Separations in Microfabricated Capillary Electrophoresis Chips Employing Focused Molecular Streams. Anal. Chem. 71 (1999), 5137-5145.
  • 20. J. P. Hernandez-Ortiz, J. J. de Pablo, and M. D. Graham, Fast Computation of Many-Particle Hydrodynamic and Electrostatic Interactions. Phys. Rev. Letters 98 (2007), 140602.
  • 21. G.A. Huber, and J.A. McCammon, Browndye: A Software Package for Brownian Dynamics. Computer Physics Communications 181 (2010), 1896-1905.
  • 22. M. Karplus and D. L. Weaver, Protein Folding Dynamics. Nature 260 (1976), 404-406.
  • 23. R. G. Larson, H. Hua, D. E. Smith, and S. Chu, Brownian Dynamics Simulations of a DNA Molecule in an Extensional Flow Field. J. Rheol. 43 (1999), 267-304.
  • 24. P. G. Martinsson and V. Rokhlin, A Fast Direct Solver for Boundary Integral Equations in Two Dimensions. J. Comput. Phys. 205 (2005), no. 1, 1-23. MR 2132300 (2005k:65292)
  • 25. P. G. Martinsson and V. Rokhlin, An Accelerated Kernel-Independent Fast Multipole Method in One Dimensions. SIAM J. Sci. Comput. 29 (2007), 1160-1178. MR 2318701 (2008f:65084)
  • 26. J . A. McCammon, J. M. Deutch, and B. U. Felderhof, Frictional Properties of Multisubunit Structures. Biopolymers 14 (1975), 2613-2623.
  • 27. D. Petera and M. Muthukumar, Brownian Dynamics Dimulation of Bead-rod Chains under Shear with Hydrodynamic Interaction. J. Chem. Phys. 111 (1999), 7614-7623.
  • 28. J. Rotne and S. Prager, Variational Treatment of Hydrodynamic Interaction in Polymers. J. Chem. Phys. 50 (1969), 4831-4837.
  • 29. A. Tornberg and L. Greengard, A Fast Multipole Method for the Three-dimensional Stokes Equations. J. Comput. Phys. 227 (2008), no. 3, 1613-1619. MR 2450963 (2009g:76110)
  • 30. L. N. Trefethen, Spectral Methods in Matlab, SIAM (2000). MR 1776072 (2001c:65001)
  • 31. L. N. Trefethen and D. Bau, Numerical Linear Algebra, SIAM, Philadelphia, 1997. MR 1444820 (98k:65002)
  • 32. P. G. Wolynes and J. M. Deutch, Slip Boundary Conditions and the Hydrodynamic Effect on Diffusion Controlled Reactions. J. Chem. Phys. 65 (1976), 450-454.
  • 33. P. G. Wolynes and J. M. Deutch, Dynamical Orientation Correlations in Solution. J. Chem. Phys. 67 (1977), 733-741.
  • 34. H. Yamakawa, Transport Properties of Polymer Chains in Dilute Solution: Hydrodynamic Interaction. J. Chem. Phys. 53 (1970), 436-443.
  • 35. L. Ying, G. Biros, and D. Zorin, A Kernel-Independent Adaptive Fast Multipole Algorithm in Two and Three Dimensions. J. Comp. Phys. 196 (2004), 591-626. MR 2054351 (2005d:65235)
  • 36. B. Zhang, Integral-Equation-Based Fast Algorithms and Graph-Theoretic Methods for Large-Scale Simulations. PhD thesis, University of North Carolina, Chapel Hill, 2010.
  • 37. Y. Zhou and Y. Saad, A Chebyshev-Davidson Algorithm for Large Symmetric Eigenvalue Problems. SIAM J. Matrix Anal. App. 29 (2007), 954-971. MR 2365900 (2008k:65081)
  • 38. Y. Zhou and R. C. Li, Bounding the Spectrum of Large Hermitian Matrices. Linear Algebra and its App. 435 (2011), 480-493. MR 2794587

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 76M35, 65Z05, 65C60, 65F60

Retrieve articles in all journals with MSC (2010): 76M35, 65Z05, 65C60, 65F60

Additional Information

Shidong Jiang
Affiliation: Department of Mathematical Sciences, New Jersey Institute of Technology, Newark, New Jersey 07102

Zhi Liang
Affiliation: Department of Mathematical Sciences, New Jersey Institute of Technology, Newark, New Jersey 07102

Jingfang Huang
Affiliation: Department of Mathematics, University of North Carolina at Chapel Hill, Chapel Hill, North Carolina 27599

Received by editor(s): July 20, 2011
Received by editor(s) in revised form: December 1, 2011
Published electronically: February 27, 2013
Additional Notes: The first author was supported in part by NSF under grant CCF-0905395
The third author was supported by NSF under grant CCF-0905473. The author’s support is thankfully acknowledged
Article copyright: © Copyright 2013 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society