First two Solutions of O(N2) Computational Complexity
1) Ignore it and implement straightforwardly on a conventional computer
2) Note that one can build special purpose parallel machines as need less communication bandwidth (and just one dimensional pipeline) and much less memory per CPU power than for general purpose (parallel) computer
- parallel algorithm well known and incredibly efficient
- This is approach of GRAPE (Gravity Pipeline) machine which could be about a factor of 100 more cost effective for astrophysics on large problems