University of Twente Student Theses
A Simplified Study on Accelerated Particle Simulation Using the Fast Multipole Method
Thakur, Mayank (2024) A Simplified Study on Accelerated Particle Simulation Using the Fast Multipole Method.
|
PDF
1MB |
| Abstract: | The Fast Multipole Method (FMM) represents a groundbreaking algorithm in computational physics, drastically reducing the computational complexity of potential calculations from $O(nm)$ to $O(n+m)$, for a system with $n$ sources and $m$ target points. This thesis explores the mathematical foundations and practical implementation of the FMM for accelerated particle simulations. We begin by formulating the problem of calculating potentials generated by a set of sources and review the limitations of naive algorithms. Through a detailed examination of the multipole and local expansions and their associated error bounds and translation operators, we establish the theoretical underpinnings of the FMM. Our study involves implementing and testing simplified versions of the FMM, focusing on configurations where sources and targets are well-separated, thereby avoiding the need for a quadtree data structure. The results confirm the FMM's expected linear complexity and its ability to trade accuracy for speed with high granularity. We also investigate the method's performance with randomly distributed particles. |
| Item Type: | Essay (Bachelor) |
| Faculty: | EEMCS: Electrical Engineering, Mathematics and Computer Science |
| Subject: | 31 mathematics, 54 computer science |
| Programme: | Computer Science BSc (56964) |
| Link to this item: | https://purl.utwente.nl/essays/103501 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page