算法种类繁多；Barnes Hut是一种流行的方法，而快速多极方法是一种更复杂的替代方法。$\mathcal{O}(N \log N)$$\mathcal{O}(N)$

这两种方法都使用树数据结构，其中节点基本上只与树的每一层的最近邻居交互。您可以考虑在足够深度的一组进程之间拆分树，然后让它们仅在最高级别进行协作。

您可以在此处找到一篇讨论千万亿次机器上的 FMM 的最新论文。

看看快速多极法。它具有高度可扩展性和。它允许在精度和成本之间进行权衡。 这是一个在 GPU 集群上以 42 Tflops 运行的示例。$O(n)$

作为替代来源，您还可以查看基于网格的 Ewald-like 方法。“粒子网格”方法（如 PPPM 和平滑粒子网格 Ewald）的起源在于天体物理学的星系模拟；与收费的联系是一个无意的副作用（只是碰巧最终超过了最初的使用）。

最近，也有一些关于多级求和方法的文献，这些方法在精神上类似于快速多极方法和 Barnes-Hut，但可能在不同的情况下提供优势（更通用和灵活的几何形状，一些效率增益等）。

对于经典的引力 n 体问题，我认为以下两篇论文很好地讨论了力评估步骤的并行实现的内容。尽管这些论文讨论了 GPU 的实现，但它们在讨论并行性并提供了算法的细节方面做得很好：

Nyland、Harris 和 Prins 的这篇论文介绍了用于 GPU 的 CUDA 中的直接 n 体算法。

Yokota 和 Barba的另一篇论文在 GPU 计算的背景下也对树代码和快速多极算法进行了很好的讨论

您关于n 体数值模拟的准确性的问题涉及更多，并且有很多重要的细节，一个答案可以产生几本书。我认为最好的办法是给你一些参考书目。我建议：

Sverre J. Aarseth 的引力 N 体模拟

霍克尼和伊斯特伍德使用粒子的计算机模拟。（抱歉没有pdf版本）