首页 |  期刊介绍 |  编委会 |  投稿指南 |  期刊订阅 |  下载中心 |  留言板 |  联系我们 |  重点论文 |  在线办公 |
 计算数学  2011, Vol. 33 Issue (2): 145-156    DOI:
 论文 最新目录 | 下期目录 | 过刊浏览 | 高级检索 Previous Articles  |  Next Articles

FAST INTERPOLATION FOR MULTILEVEL FAST MULTIPOLE METHOD
Wang Wu, Feng Yangde, Chi Xuebin
Supercomputing Center, Computer Network Information Center, Chinese Academy of Sciences, Beijing 100190, China
 全文: PDF (819 KB)   HTML (1 KB)   输出: BibTeX | EndNote (RIS)      背景资料

Abstract

Multilevel fast multipole method (MLFMM) can be used to accelerate the iterative solution of integral equation deduced from Maxwell equations or Helmholtz-type equation, with a theoretical complexity of O(N logN), where N is the number of unknowns. MLFMM depends on fast calculating the translation term at each level, and interpolations between levels during upward and downward pass phases. The one-dimentional fast multipole method (FMM1D) similar to which used in N-body problem is introduced in this paper.
Fast Lagrange interpolation algorithm based on FMM1D can reduce the computing time of translation operator from O(N1.5) to O(N). Fast spectrum interpolation with a hybrid FFT-FMM1D method can also reduce the computing complexity of interpolations between levels from O(K2) to O(K logK), where K is the number of sample points. The numerical results of MLFMM based on these two fast inperpolation methods have near linear time performances and accurate solutions.

 引用本文: . 多层快速多极子方法的快速插值[J]. 计算数学, 2011, 33(2): 145-156. . FAST INTERPOLATION FOR MULTILEVEL FAST MULTIPOLE METHOD[J]. Mathematica Numerica Sinica, 2011, 33(2): 145-156.

 [1] Greengard L, Rokhlin V. A fast algorithm for particle simulations[J]. J. Comput. Phys., 1987, 73(2): 325-348. [2] Rokhlin V. Rapid solution of integral equations of scattering theory in two dimensions[J]. J. Comput. Phys., 1990, 86(2): 414-439. [3] Chew W C, Jin J M, etc., Fast and efficeint Algorithms for computational electromagnetics[M]. New York, NY: Artech House, 2001, 39-61. [4] Velamparambil S, Chew W C. A fast polynomial representation for the translation operators of an MLFMA[J]. Microwave and Optical Technology Letters, 2001, 28(5): 298-303. 3.0.CO;2-L target="_blank"> [5] Yarvin N, Rokhlin V. An improved fast multipole algorithm for potential fields on one-dimensional structures[J]. SIAM J. Numer. Anal., 1999, 36(2): 629-666. [6] Healy D, Rockmore D, etc., FFTs for the 2-sphere: improvements and variations[J]. J. Fourier Anal. Appl., 2003, 9(4): 341-385. [7] Dutt A, Gu M, Rokhlin V. Fast algorithms for polynomial interpolation, integration, and differ-entiation[J]. SIAM J. Numer. Anal., 1996, 33(55): 1689-1711. [8] Darve E. The fast multipole method: numerical implementation[J]. J. Comput. Phys., 2000, 160(1): 195-240. [9] Holmes S, Featherstone W. A unified approach to the Clenshaw summation and the recursive computation of very high degree and order normalised associated Legendre functions[J]. Journal of Geodesy, 2002, 76(5): 279-299. [10] Alpert B, Chien R. A Fast spherical filter with uniform resolution[J]. J. Comput. Phys., 1997, 136(2):580-584. [11] Rokhlin V, Tygert M. Fast algorithms for spherical harmonic expansions[J], SIAM J. Sci. Comput., 2006, 27(6): 1903-1928. [12] Berrut J P, Trefethen L N. Barycentric Lagrange interpolation[J]. SIAM Rev., 2004, 46(3): 501-517.
 [1] 段艳婷, 王连堂, 徐建丽. 二维Helmholtz方程外问题的数值解法[J]. 计算数学, 2011, 32(1): 57-63. [2] 罗兴钧, 李繁春, 杨素华. 最优投影策略下解病态积分方程的快速迭代算法[J]. 计算数学, 2011, 33(1): 1-14. [3] 闵涛, 武苗, 卢宏鹏, 杨晓莉, 许迅雷. 求解Symm积分方程的信赖域Lanczos法[J]. 计算数学, 2010, 31(4): 253-258. [4] 杨素华,罗兴钧,邱修峰,. 求Abel型积分方程数值解的正则化方法[J]. 计算数学, 2008, 30(1): 17-24. [5] 王武,冯仰德,迟学斌. 电场积分方程的快速求解[J]. 计算数学, 2008, 29(1): 15-24. [6] 余越昕,李寿佛. Volterra延迟积分方程单支θ-方法的数值稳定性[J]. 计算数学, 2005, 26(4): 262-268. [7] 张耀明,温卫东,王利民,赵熙强,孙翠莲. 平面定常Stokes问题的无奇异第一类边界积分方程[J]. 计算数学, 2005, 27(1): 1-10. [8] 马万,王兴华. 多元积分方程自适应解法的最优化[J]. 计算数学, 2004, 26(2): 161-168. [9] 黄晋,吕涛. 曲边多角形域上第一类边界积分方程的机械求积算法与分裂外推[J]. 计算数学, 2004, 26(1): 51-60. [10] 冯象初,付瑜,宋国乡. 边界曲线积分方程的小波解法[J]. 计算数学, 2002, 24(1): 21-26. [11] 吕涛,黄晋. 解平面弹性力学问题的边界积分方程的机械求积方法及其外推[J]. 计算数学, 2001, 23(4): 491-502. [12] 吕涛,黄晋. 解第一类边界积分方程的高精度机械求积法与外推[J]. 计算数学, 2000, 22(1): 59-72.
 Copyright 2008 计算数学 版权所有 中国科学院数学与系统科学研究院 《计算数学》编辑部 北京2719信箱 (100190) Email: gxy@lsec.cc.ac.cn 本系统由北京玛格泰克科技发展有限公司设计开发 技术支持: 010-62662699 E-mail:support@magtech.com.cn 京ICP备05002806号-10