Implementation of Fast Multipole Algorithm on Special-Purpose Computer MDGRAPE-2

摘要

N-body simulation is a time consuming task in which force calculation part is most dominant part. The simplest and most accurate algorithm for force calculation is direct summation which has time complexity O(N~2). It is not practically suitable for large-scale simulations on most general-purpose computers. To cut down cost of force calculation one applies fast algorithms or performs force calculation on special-purpose hardware. GRAPE is a special-purpose computer designed for force calculation between point-charge or point-mass particles. It performs force calculation much faster than general-purpose computers of similar cost. However the time complexity of direct force calculation on GRAPE is still O(N~2). In this paper, we deal with the implementation of fast multipole algorithm whose time complexity is O(N) on special-purpose computer MDGRAPE-2. We present our experimental results for up to four millions particles system. Performance and accuracy of FMM on GRAPE is presented. Comparison of FMM with treecode and direct summation on GRAPE is also given.