{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T22:59:23Z","timestamp":1777676363300,"version":"3.51.4"},"reference-count":22,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2008,5,1]],"date-time":"2008-05-01T00:00:00Z","timestamp":1209600000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The International Journal of High Performance Computing Applications"],"published-print":{"date-parts":[[2008,5]]},"abstract":"<jats:p>\n                    We have implemented the fast multipole method (FMM) on a special-purpose computer GRAPE (GRAvity piPE). The FMM is one of the fastest approximate algorithms to calculate forces among particles. Its calculation cost scales as O( N), while the naive algorithm scales as O( N\n                    <jats:sup>2<\/jats:sup>\n                    ). Here, N is the number of particles in the system. GRAPE is hardware dedicated to the calculation of Coulombic or gravitational forces among particles. GRAPE's calculation speed is 100\u20141000 times faster than that of conventional computers of the same price, though it cannot handle anything but force calculation. We can expect significant speedup by the combination of the fast algorithm and the fast hardware. However, a straightforward implementation of the algorithm actually runs on GRAPE at rather modest speed. This is because of the limited functionality of the hardware. Since GRAPE can handle particle forces only, just a small fraction of the overall calculation procedure can be put on it. The remaining part must be performed on a conventional computer connected to GRAPE. In order to take full advantage of the dedicated hardware, we modified the FMM using the pseudoparticle multipole method and Anderson's method. In the modified algorithm, multipole and local expansions are expressed by distribution of a small number of imaginary particles (pseudoparticles), and thus they can be evaluated by GRAPE. Results of numerical experiments on ordinary GRAPE systems show that, for large- N systems ( N \u2265 10\n                    <jats:sup>5<\/jats:sup>\n                    ), GRAPE accelerates the FMM by a factor ranging from 3 for low accuracy (RMS relative force error ~10\n                    <jats:sup>\u20142<\/jats:sup>\n                    ) to 60 for high accuracy (RMS relative force error ~10\n                    <jats:sup>\u2014 5<\/jats:sup>\n                    ). Performance of the FMM on GRAPE exceeds that of Barnes\u2014Hut treecode on GRAPE at high accuracy, in case of close-to-uniform distribution of particles. However, in the same experimental environment the treecode outperforms the FMM for inhomogeneous distribution of particles.\n                  <\/jats:p>","DOI":"10.1177\/1094342008090912","type":"journal-article","created":{"date-parts":[[2008,4,15]],"date-time":"2008-04-15T09:57:52Z","timestamp":1208253472000},"page":"194-205","source":"Crossref","is-referenced-by-count":3,"title":["Acceleration of Fast Multipole Method Using Special-Purpose Computer Grape"],"prefix":"10.1177","volume":"22","author":[{"family":"Nguyen Hai Chau","sequence":"first","affiliation":[{"name":"College of Technology, Vietnam National University, 144 Xuan Thuy, Cau\r                        Giay, Hanoi, Vietnam, ,"}]},{"given":"Atsushi","family":"Kawai","sequence":"additional","affiliation":[{"name":"K&f Computing Research Co., 1-21-6-407, Kojima-Cho, Chofu, Tokyo, Japan 182-0026"}]},{"given":"Toshikazu","family":"Ebisuzaki","sequence":"additional","affiliation":[{"name":"Computational Astrophysics Laboratory, Institute of Physical and Chemical\r                        Research, (RIKEN), Hirosawa 2-1, Wako-shi, Saitama, Japan 351-0198"}]}],"member":"179","published-online":{"date-parts":[[2008,5,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1002\/jcc.10193"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/0913055"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(90)90232-P"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1038\/324446a0"},{"key":"atypb5","volume-title":"Proceedings of the 6th World Multiconference on Systemics, Cybernetics and Informatics 2002 (SCI2002)","author":"Chau, N.H."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1086\/383192"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1093\/pasj\/57.6.1009"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(87)90140-9"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492900002725"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/BF02711518"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1177\/109434209601000101"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1086\/319638"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1086\/381391"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/S0010-4655(02)00157-1"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/S1093-3263(02)00125-0"},{"key":"atypb16","first-page":"621","volume":"43","author":"Makino, J.","year":"1991","journal-title":"Publications of the Astronomical Society of Japan"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.1999.6226"},{"key":"atypb18","volume-title":"Scientific simulations with special-purpose computers - The GRAPE systems","author":"Makino, J.","year":"1998"},{"key":"atypb19","volume-title":"Numerical recipes in C - The art of scientific computing","author":"Press, W.H.","year":"1992","edition":"2"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1038\/345033a0"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/S0010-4655(03)00349-7"},{"key":"atypb22","volume-title":"Proceedings of the Fourth IEEE International Symposium on High Performance Distributed Computing 1995 (HPDC 95)","author":"Wrankin, W.T."}],"container-title":["The International Journal of High Performance Computing Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342008090912","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342008090912","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T08:18:37Z","timestamp":1777450717000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/1094342008090912"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,5]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,5]]}},"alternative-id":["10.1177\/1094342008090912"],"URL":"https:\/\/doi.org\/10.1177\/1094342008090912","relation":{},"ISSN":["1094-3420","1741-2846"],"issn-type":[{"value":"1094-3420","type":"print"},{"value":"1741-2846","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,5]]}}}