TY - JOUR

T1 - A fast algorithm for brownian dynamics simulation with hydrodynamic interactions

AU - Jiang, Shidong

AU - Liang, Zhi

AU - Huang, Jingfang

N1 - Copyright:
Copyright 2013 Elsevier B.V., All rights reserved.

PY - 2013

Y1 - 2013

N2 - 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 × 3N matrix and thus requires O(N3) 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(√KN) with k 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 k 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 analy-sis with certain spatial correlations and model reduction in dynamic control theory.

AB - 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 × 3N matrix and thus requires O(N3) 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(√KN) with k 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 k 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 analy-sis with certain spatial correlations and model reduction in dynamic control theory.

UR - http://www.scopus.com/inward/record.url?scp=84878175206&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84878175206&partnerID=8YFLogxK

U2 - 10.1090/S0025-5718-2013-02672-5

DO - 10.1090/S0025-5718-2013-02672-5

M3 - Article

AN - SCOPUS:84878175206

VL - 82

SP - 1631

EP - 1645

JO - Mathematics of Computation

JF - Mathematics of Computation

SN - 0025-5718

IS - 283

ER -