Parallel Algorithm in Fast Multipole I
Parallelism is clear -- update particles in parallel but what about communication?
It requires a thoughtful algorithm but can efficiently fetch information needed.
- Fetch all the information needed by ANY particle in a given processor as multipole approach implies that particles tend to need same long range components if nearby
- call this “locally essential” data
- cf. O(N) multipole-multipole approach
Effectively top of tree replicated in all processors and tey just differ near bottom which is expanded in a way that depends on where processor is