A fast algorithm for brownian dynamics simulation with hydrodynamic interactions

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(N³) 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.