# 🔄 Recursive Approximation Algorithm

# Motivation

aka Fast Multipole Method, is used to speed up an N-body problem. We are primarily interested in FFM since it can be used in the following areas:

* The T-matrix method solves electromagnetic scattering at spherical and non-spherical particles. Due to large matrix-vector multiplications, the toll on hardware is significant, so a speed-up is always appreciated!
* 2D ray tracing on fractal surfaces for self-healing. On airless bodies, mutually visible surfaces can heat up each other through the reflected light. This is a significant effect when looking at surfaces in the thermal infrared region since the temperature depends on the body and its roughness.

Multiple FMM algorithms can be used, and this thesis can be tailored to your degree of interest in a certain topic.

* There is a lack of GPU-accelerated implementations, so one could look into implementing a rudimentary algorithm in Python using JAX so it can be tested on CPU and GPU and maybe even extended to TPUs in the future.
* The already present implementations can be used and applied to one of the two topics above, but mainly to the T-Matrix method since I am more familiar with it. Our light scattering framework [YASF](https://github.com/AGBV/YASF/) can incorporate one implemented algorithm, and it can be further tested and validated with this approach.

# Literature

* [Here's](https://andyljones.com/posts/multipole-methods.html) a nice explanation of FMM. The code for a potential GPU implementation in Python can be found in [this](https://github.com/andyljones/pybbfmm) repository.
* [An Overview of Fast Multipole Methods](https://ics.uci.edu/\~ihler/papers/ihler_area.pdf)
* [A short course on fast multipole methods](https://math.nyu.edu/\~greengar/shortcourse_fmm.pdf)
* [Fast Multipole Methods for the Helmholtz Equation in Three Dimensions](https://www.sciencedirect.com/book/9780080443713/fast-multipole-methods-for-the-helmholtz-equation-in-three-dimensions)
* [A GPU-parallelized interpolation-based fast multipole method for the relativistic space-charge field calculation](https://www.sciencedirect.com/science/article/pii/S0010465523001704)
* [A CUDA fast multipole method with highly efficient M2L far field evaluation](https://www.mpinat.mpg.de/634623/Kohnke_2021_IJHPCA.pdf)

---

**Documents**

- [Testbed for 3D reconstruction](https://notes.bv.e-technik.tu-dortmund.de/s/72da764c-c4ab-4489-bd58-b1f36c300d0e/doc/testbed-for-3d-reconstruction-P3rfIpv6Tb)
- [Space weathering on airless exoplanets](https://notes.bv.e-technik.tu-dortmund.de/s/72da764c-c4ab-4489-bd58-b1f36c300d0e/doc/space-weathering-on-airless-exoplanets-hWL1mEyXxX)
- [Hyper Illumination on Local and Global Scales](https://notes.bv.e-technik.tu-dortmund.de/s/72da764c-c4ab-4489-bd58-b1f36c300d0e/doc/hyper-illumination-on-local-and-global-scales-qLMTJQRCGP)
- [(RESERVED) MoonPoints: Automatically Detecting Points for Co-Registration in Planetary Images](https://notes.bv.e-technik.tu-dortmund.de/s/72da764c-c4ab-4489-bd58-b1f36c300d0e/doc/reserved-moonpoints-automatically-detecting-points-for-co-registration-in-planetary-images-bPHxhOZff4)
- [(RESERVED) Reconstruction of 3D Particle Clusters Using 2D TEM Images](https://notes.bv.e-technik.tu-dortmund.de/s/72da764c-c4ab-4489-bd58-b1f36c300d0e/doc/reserved-reconstruction-of-3d-particle-clusters-using-2d-tem-images-wWZZ7ezGuF)
- [Recursive Approximation Algorithm](https://notes.bv.e-technik.tu-dortmund.de/s/72da764c-c4ab-4489-bd58-b1f36c300d0e/doc/recursive-approximation-algorithm-qRcWUPlNUK)