多层快速多极子方法的快速插值
FAST INTERPOLATION FOR MULTILEVEL FAST MULTIPOLE METHOD
查看参考文献12篇
|
文摘
|
多层快速多极子方法(MLFMM)可用来加速迭代求解由Maxwell方程组或Helmholtz方程导出的积分方程, 其复杂度理论上是O(NlogN), N为未知量个数.MLFMM依赖于快速计算每层的转移项, 以及上聚和下推过程中的层间插值.本文引入计算类似Ⅳ体问题的一维快速多极子方法(FMMlD).基于FMMlD的快速Lagrange插值算法可将转移项的计算复杂度由 O(N~(1.5))降低到O(N).运用FMMlD与FFT混合的快速谱插值算法可将层间插值的计算复杂度由O(K~2)降低到O(KlogK), K为插值取样点数.数值结果显示了基于这两种快速插值的 MLFMM具有近似线性的时间复杂度 |
|
其他语种文摘
|
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 0(N log N), 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(KlogK), 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 |
|
来源
|
计算数学
,2011,33(2):145-156 【核心库】
|
|
关键词
|
积分方程
;
多层快速多极子方法
;
转移项
;
快速Lagrange插值
;
快速谱插值
|
|
地址
|
中国科学院计算机网络信息中心超级计算中心, 北京, 100190
|
|
语种
|
中文 |
|
文献类型
|
研究性论文 |
|
ISSN
|
0254-7791 |
|
学科
|
数学 |
|
基金
|
国家自然科学基金
;
国家高技术研究发展计划
;
国家973计划
|
|
文献收藏号
|
CSCD:4181593
|
参考文献 共
12
共1页
|
|
1.
Greengard L. A fast algorithm for particle simulations.
J. Comput. Phys,1987,73(2):325-348
|
被引
113
次
|
|
|
|
|
2.
Rokhlin V. Rapid solution of integral equations of scattering theory in two dimensions.
J. Comput. Phys,1990,86(2):414-439
|
被引
49
次
|
|
|
|
|
3.
Chew W C.
Fast and efficeint Algorithms for computational electromagnetics,2001:39-61
|
被引
2
次
|
|
|
|
|
4.
Velamparambil S. A fast polynomial representation for the translation operators of an MLFMA.
Microwave and Optical Technology Letters,2001,28(5):298-303
|
被引
1
次
|
|
|
|
|
5.
Yarvin N. An improved fast multipole algorithm for potential fields on one-dimensional structures.
SIAM J. Numer. Anal,1999,36(2):629-666
|
被引
2
次
|
|
|
|
|
6.
Healy D. FFTs for the 2-sphere: improvements and variations.
J. Fourier Anal. Appl,2003,9(4):341-385
|
被引
4
次
|
|
|
|
|
7.
Dutt A. Fast algorithms for polynomial interpolation, integration, and differentiation.
SIAM J. Numer. Anal,1996,33(55):1689-1711
|
被引
1
次
|
|
|
|
|
8.
Darve E. The fast multipole method: numerical implementation.
J. Comput. Phys,2000,160(1):195-240
|
被引
11
次
|
|
|
|
|
9.
Holmes S. A unified approach to the Clenshaw summation and the recursive computation of very high degree and order normalised associated Legendre functions.
Journal of Geodesy,2002,76(5):279-299
|
被引
34
次
|
|
|
|
|
10.
Alpert B. A Fast spherical filter with uniform resolution.
J. Comput. Phys,1997,136(2):580-584
|
被引
1
次
|
|
|
|
|
11.
Rokhlin V. Fast algorithms for spherical harmonic expansions.
SIAM J. Sci. Comput,2006,27(6):1903-1928
|
被引
2
次
|
|
|
|
|
12.
Berrut J P. Barycentric Lagrange interpolation.
SIAM Rev,2004,46(3):501-517
|
被引
48
次
|
|
|
|
|
了解气象卫星更多信息，请访问