Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 


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), no. 1, 1–29. MR 0406082
  • 2. Sheung Hun Cheng, Nicholas J. Higham, Charles S. Kenney, and Alan J. Laub, Approximating the logarithm of a matrix to specified accuracy, SIAM J. Matrix Anal. Appl. 22 (2001), no. 4, 1112–1125 (electronic). MR 1825853, 10.1137/S0895479899364015
  • 3. Ȧke Björck and Germund Dahlquist, Numerical methods, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1974. Translated from the Swedish by Ned Anderson; Prentice-Hall Series in Automatic Computation. MR 0368379
  • 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. William Fong and Eric Darve, The black-box fast multipole method, J. Comput. Phys. 228 (2009), no. 23, 8712–8725. MR 2558773, 10.1016/
  • 10. Bengt Fornberg, A practical guide to pseudospectral methods, Cambridge Monographs on Applied and Computational Mathematics, vol. 1, Cambridge University Press, Cambridge, 1996. MR 1386891
  • 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. Zydrunas Gimbutas and Vladimir Rokhlin, A generalized fast multipole method for nonoscillatory kernels, SIAM J. Sci. Comput. 24 (2002), no. 3, 796–817 (electronic). MR 1950512, 10.1137/S1064827500381148
  • 15. Gene H. Golub and Charles F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720
  • 16. Leslie Greengard, Denis Gueyffier, Per-Gunnar Martinsson, and Vladimir Rokhlin, Fast direct solvers for integral equations in complex three-dimensional domains, Acta Numer. 18 (2009), 243–275. MR 2506042, 10.1017/S0962492906410011
  • 17. L. Greengard and V. Rokhlin, A fast algorithm for particle simulations, J. Comput. Phys. 73 (1987), no. 2, 325–348. MR 918448, 10.1016/0021-9991(87)90140-9
  • 18. Leslie Greengard and Vladimir Rokhlin, A new version of the fast multipole method for the Laplace equation in three dimensions, Acta numerica, 1997, Acta Numer., vol. 6, Cambridge Univ. Press, Cambridge, 1997, pp. 229–269. MR 1489257, 10.1017/S0962492900002725
  • 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, 10.1016/
  • 25. P. G. Martinsson and V. Rokhlin, An accelerated kernel-independent fast multipole method in one dimension, SIAM J. Sci. Comput. 29 (2007), no. 3, 1160–1178. MR 2318701, 10.1137/060662253
  • 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. Anna-Karin Tornberg and Leslie Greengard, A fast multipole method for the three-dimensional Stokes equations, J. Comput. Phys. 227 (2008), no. 3, 1613–1619. MR 2450963, 10.1016/
  • 30. Lloyd N. Trefethen, Spectral methods in MATLAB, Software, Environments, and Tools, vol. 10, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2000. MR 1776072
  • 31. Lloyd N. Trefethen and David Bau III, Numerical linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1444820
  • 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. Lexing Ying, George Biros, and Denis Zorin, A kernel-independent adaptive fast multipole algorithm in two and three dimensions, J. Comput. Phys. 196 (2004), no. 2, 591–626. MR 2054351, 10.1016/
  • 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. Yunkai Zhou and Yousef Saad, A Chebyshev-Davidson algorithm for large symmetric eigenproblems, SIAM J. Matrix Anal. Appl. 29 (2007), no. 3, 954–971 (electronic). MR 2365900, 10.1137/050630404
  • 38. Yunkai Zhou and Ren-Cang Li, Bounding the spectrum of large Hermitian matrices, Linear Algebra Appl. 435 (2011), no. 3, 480–493. MR 2794587, 10.1016/j.laa.2010.06.034

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.