Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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
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?)


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
Email: shidong.jiang@njit.edu

Zhi Liang
Affiliation: Department of Mathematical Sciences, New Jersey Institute of Technology, Newark, New Jersey 07102
Email: zl28@njit.edu

Jingfang Huang
Affiliation: Department of Mathematics, University of North Carolina at Chapel Hill, Chapel Hill, North Carolina 27599
Email: huang@amath.unc.edu

DOI: http://dx.doi.org/10.1090/S0025-5718-2013-02672-5
PII: S 0025-5718(2013)02672-5
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.