Parallel Multipole Expansion Algorithms and Their Biology Applications

N-body pairwise interactions are ubiquitous in scientific areas such as astrophysics, fluids mechanics, electrical engineering, molecular biology, etc. Computing these interactions using direct sum of an O(N) cost is expensive, whereas multipole expansion methods, such as the fast multipole method (FMM) or treecode, can reduce the cost to O(N) or O(N log N). This thesis focuses on developing numerical algorithms of Cartesian FMM and treecode, as well as using these algorithms to directly or implicitly solve biological problems involving pairwise interactions. This thesis consists of the following topics. 1) A cyclic parallel scheme is developed to handle the load balancing issue, which is happened in the treecode accelerated N-body problem for solving molecular electrostatic potentials. 2) We design a block diagonal preconditioning scheme using a tree structure to accelerate the iterative solver. 3) The Cartesian fast multipole method is applied to accelerate the boundary integral form of the Poisson-Boltzmann equation. 4) We study the reformulation of the Poisson-Boltzmann equation by regularizing the singular kernels in the boundary integral equations. 5) We investigate the multipole expansion to accelerate the calculation of electrostatic interaction in the Monte Carlo chromatin packing simulation. 6) We propose an idea to use the Cartesian FMM to model the crowded cellular environments. 7) We introduce a procedure to use TABI-PB to calculate pKa values. 8) The last project studies the TABI-PB solver to compute the protein binding energies.