Treecodes for potential and force approximations /
| Main Author: | |
|---|---|
| Other Authors: | , |
| Format: | Thesis eBook |
| Language: | English |
| Published: |
[College Station, Tex.] :
[Texas A&M University],
[2010]
|
| Subjects: | |
| Online Access: | Link to OAK Trust copy |
| Abstract: | N-body problems encompass a variety of fields such as electrostatics, molecular biology and astrophysics. If there are N particles in the system, the brute force algorithm for these problems based on particle-particle interaction takes O(N2), which is clearly expensive for large values of N. There have been some approximation algorithms like the Barnes-Hut Method and the Fast Multipole Method (FMM) proposed for these problems to reduce the complexity. However, the applicability of these algorithms are limited to operators with analytic multipole expansions or restricted to simulations involving low accuracy. The shortcoming of N-body treecodes are more evident for particles in motion where the movement of the particles are not considered when evaluating the potential. If the displacement of the particles are small, then updating the multipole coefficients for all the nodes in the tree may not be required for computing the potential to a reasonable accuracy. This study focuses on some of the limitations of the existing approximation schemes and presents new algorithms that can be used for N-body simulations to efficiently compute potentials and forces. In the case of electrostatics, existing algorithms use Cartesian coordinates to evaluate the potentials of the form r⁸́₂, where 1. The use of such coordinates to separate the variables results in cumbersome expressions and does not exploit the inherent spherical symmetry found in these kernels. For such potentials, we provide a new multipole expansion series and construct a method which is asymptotically superior than the current treecodes. The advantage of this expansion series is further demonstrated by an algorithm that can compute the forces to the desired accuracy. For particles in motion, we introduce a new method in which we retain the multipole coefficients when performing multipole updates (to the parent nodes) at every time step. This results in considerable savings in time while maintaining the accuracy. We further illustrate the efficiency of our algorithms through numerical experiments. |
|---|---|
| Item Description: | "Major Subject: Computer Science" Title from author supplied metadata (automated record created 2010-03-12 12:08:51). Electronic resource. |
| Physical Description: | 1 online resource. |
| Bibliography: | Includes bibliographical references. |