高速多重極展開法とツリー法 : 多体シミュレーションのための高速算法(<特集>数値計算)  [in Japanese] Fast Multipole Method and Tree Method : Fast Algorithms for Many Body Simulations(<Special Topics>Numerical Computation)  [in Japanese]

Access this Article

Search this Article

Author(s)

Abstract

I overview the Fast Multipole Method (FMM) and the Barnes-Hut tree method. These algorithms evaluate mutual gravitational interaction between N particles in O(N) or O(N log N) times, respectively. I present basic algorithms as well as recent developments, such as Anderson's method of using Poisson's formula, the use of FFT, and other optimization techniques. I also summarize the current states of two algorithms. Though FMM with O(N) scaling is theoretically preferred over O(N log N) tree method, comparisons of existing implementations proved otherwise. This result is not surprizing, since the calculation cost of FMM scales as O(Np^2) where p is the order of expansion, while that of the tree method scales as O(N log Np).

Journal

  • Bulletin of the Japan Society for Industrial and Applied Mathematics

    Bulletin of the Japan Society for Industrial and Applied Mathematics 8(4), 277-287, 1998

    The Japan Society for Industrial and Applied Mathematics

References:  18

Cited by:  1

Codes

  • NII Article ID (NAID)
    110007391030
  • NII NACSIS-CAT ID (NCID)
    AN10288886
  • Text Lang
    JPN
  • Article Type
    Journal Article
  • ISSN
    09172270
  • NDL Article ID
    4625277
  • NDL Source Classification
    ZM31(科学技術--数学)
  • NDL Call No.
    Z15-726
  • Data Source
    CJP  CJPref  NDL  NII-ELS  J-STAGE 
Page Top