Articles via Databases
Articles via Journals
Online Catalog
E-books
Research & Information Literacy
Interlibrary loan
Theses & Dissertations
Collections
Policies
Services
About / Contact Us
Administration
Littman Architecture Library

The New Jersey Institute of Technology's
Electronic Theses & Dissertations Project

Title: Fast algorithms for Brownian dynamics simulation with hydrodynamic interactions
Author: Liang, Zhi
View Online: njit-etd2012-088
(x, 65 pages ~ 0.5 MB pdf)
Department: Department of Mathematical Sciences
Degree: Doctor of Philosophy
Program: Mathematical Sciences
Document Type: Dissertation
Advisory Committee: Jiang, Shidong (Committee chair)
Huang, Jingfang (Committee member)
Petropoulos, Peter G. (Committee member)
Siegel, Michael (Committee member)
Young, Yuan N. (Committee member)
Date: 2012-08
Keywords: Square root matrix
Hydrodynamics interaction
Fast multipole method
Rotke-Prager-Yamakawa tensor
Brownian dynamics
Lanzos iteration
Availability: Unrestricted
Abstract:

In the Brownian dynamics simulation with hydrodynamic interactions, one needs to generate the total displacement vectors of Brownian particles consisting of two parts: a deterministic part which is proportional to the product of the Rotne-Prager-Yamakawa (RPY) tensor D [1, 2] and the given external forces F; and a hydrodynamically correlated random part whose covariance is proportional to the RPY tensor. To be more precise, one needs to calculate Du for a given vector u and compute √Dv for a normally distributed random vector v. For an arbitrary N-particle configuration, D is a 3N x 3N matrix and u, v are vectors of length 3N. Thus, classical algorithms require O(N2) operations for computing Du and O(N3) operations for computing √Dv, which are prohibitively expensive and render large scale simulations impossible since one needs to carry out these calculations many times in a Brownian dynamics simulation.

In this dissertation, we first present two fast multipole methods (FMM) for computing Du. The first FMM is a simple application of the kernel independent FMM (KIFMM) developed by Ying, Biros, and Zorin [3], which requires 9 scalar FMM calls. The second FMM, similar to the FMM for Stokeslet developed by Tornberg and Greengard [4], decomposes the RPY tensor into harmonic potentials and its derivatives, and thus requires only four harmonic FMM calls. Both FMMs reduce the computational cost of Du from O(N2) to O(N) for an arbitrary N-particle configuration.

We then discuss several methods of computing √Dv, which are all based on the Krylov subspace approximations, that is, replacing √Dv by p(D)v with p(D) a low degree polynomial in D. We first show rigorously that the popular Chebyshev spectral approximation method (see, for example, [5, 6]) requires √κ log 1/ε terms for a desired precision E, where K is the condition number of the RPY tensor D. In the Chebyshev spectral approximation method, one also needs to estimate the extreme eigenvalues of D. We have considered several methods: the classical Lanczos method, the Chebyshev-Davidson method, and the safeguarded Lanczos method proposed by Zhou and Li [7]. Our numerical experiments indicate that K is usually very small when the particles are distributed uniformly with low density, and that the safeguarded Lanczos method is most effective for our cases with very little additional computational cost. Thus, when combined with the FMMs we described earlier, the Chebyshev approximation method with safeguarded Lanczos method as eigenvalue estimators essentially reduces the cost of computing √Dv from O(N3) to O(N) for most practical particle configurations. Finally, we propose to combine the so-called spectral Lanczos decomposition method (SLDM) (see, for example, [8]) and the FMMs to compute √Dv. Our numerical experiments show that the SLDM is generally more efficient than the popular Chebyshev spectral approximation method.

The fast algorithms developed in this dissertation 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. Moreover, the algorithms can be extended to speed up the computation involving the matrix square root for many other matrices, which has potential applications in areas such as statistical analysis with certain spatial correlations and model reduction in dynamic control theory.


If you have any questions please contact the ETD Team, libetd@njit.edu.

 
Browse ETDs by Adviser
Browse ETDs by Author
Browse ETDs by Program
Browse ETDs by Title
Browse ETDs by Year
ETD Policies & Procedures
ETD FAQ's
ETD home

Request a Scan
NDLTD

NJIT's ETD project was given an ACRL/NJ Technology Innovation Honorable Mention Award in spring 2003