计算数学
       首页 |  期刊介绍 |  编委会 |  投稿指南 |  期刊订阅 |  下载中心 |  留言板 |  联系我们 |  在线办公 | 
计算数学  2011, Vol. 33 Issue (2): 145-156    DOI:
论文 最新目录 | 下期目录 | 过刊浏览 | 高级检索 Previous Articles  |  Next Articles  
多层快速多极子方法的快速插值
王武, 冯仰德, 迟学斌
中国科学院计算机网络信息中心超级计算中心, 北京 100190
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)      背景资料
摘要 

多层快速多极子方法(MLFMM)可用来加速迭代求解由Maxwell方程组 或Helmholtz方程导出的积分方程,其复杂度理论上是O(Nlog N), N为未知量个数. MLFMM依赖于快速计算每层的转移项, 以及上聚和下推过程中的层间插值.本文引入计算类似N体问题的一维快速多极 子方法(FMM1D).基于FMM1D的快速Lagrange插值算法可将转移项的计算复杂度由O(N1.5)降低到O(N).运用FMM1D与FFT混合的快速谱插值算法可将层间插值的计算复杂度由O(K2)降低到O(Klog L), K为插值取样点数.数值结果显示了基于这两种快速插值的MLFMM具有近似线性的时间复杂度.

服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
关键词积分方程   多层快速多极子方法   转移项   快速Lagrange插值   快速谱插值     
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.

Key wordsintegral equation   multilevel fast multipole method   translation term   fast Lagrange interpolation   fast spectrum interpolation   
收稿日期: 2009-12-04;
基金资助:

国家自然科学基金(10972215, 60873113), 国家高技术研究发展计划(2009AA01A134, 2010AA012301)和国家重点基础研究发展计划(2010CB832702)资助项目.

引用本文:   
. 多层快速多极子方法的快速插值[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