An efficient blocking M2L translation for low-frequency fast multipole method in three dimensions
详细信息 查看全文
- 作者：Toru Takahashi ; ttaka@nuem.nagoya-u.ac.jp" class="auth_mail" title="E-mail the corresponding author ; Yuta Shimba ; Hiroshi Isakari ; Toshiro Matsumoto
- 关键词：Fast multipole method ; Multipole-to-local translation ; Congruent transformation ; Boundary element method ; Numerical linear algebra ; Matrix&ndash ; matrix product ; Cache/register blocking ; BLAS
- 刊名：Computer Physics Communications
- 出版年：2016
- 出版时间：May 2016
- 年：2016
- 卷：202
- 期：Complete
- 页码：151-164
- 全文大小：1092 K
文摘
We propose an efficient scheme to perform the multipole-to-local (M2L) translation in the three-dimensional low-frequency fast multipole method (LFFMM). Our strategy is to combine a group of matrix–vector products associated with M2L translation into a matrix–matrix product in order to diminish the memory traffic. For this purpose, we first developed a grouping method (termed as internal blocking) based on the congruent transformations (rotational and reflectional symmetries) of M2L-translators for each target box in the FMM hierarchy (adaptive octree). Next, we considered another method of grouping (termed as external blocking) that was able to handle M2L translations for multiple target boxes collectively by using the translational invariance of the M2L translation. By combining these internal and external blockings, the M2L translation can be performed efficiently whilst preservingthe numerical accuracy exactly. We assessed the proposed blocking scheme numerically and applied it to the boundary integral equation method to solve electromagnetic scattering problems for perfectly electrical conductor. From the numerical results, it was found that the proposed M2L scheme achieved a few times speedup compared to the non-blocking scheme.