计算数学
計算數學
계산수학
MATHEMATICA NUMERICA SINICA
2011年
2期
145-156
,共12页
积分方程%多层快速多极子方法%转移项%快速Lagrange插值%快速谱插值
積分方程%多層快速多極子方法%轉移項%快速Lagrange插值%快速譜插值
적분방정%다층쾌속다겁자방법%전이항%쾌속Lagrange삽치%쾌속보삽치
多层快速多极子方法(MLFMM)可用来加速迭代求解由Maxwell方程组或Helmholtz方程导出的积分方程,其复杂度理论上是O(NlogN),N为未知量个数.MLFMM依赖于快速计算每层的转移项,以及上聚和下推过程中的层间插值.本文引入计算类似N体问题的一维快速多极子方法(FMM1D).基于FMM1D的快速Lagrange插值算法可将转移项的计算复杂度由O(N1.5)降低到O(N).运用FMM1D与FFT混合的快速谱插值算法可将层间插值的计算复杂度由O(K2)降低到O(K log K),K为插值取样点数.数值结果显示了基于这两种快速插值的MLFMM具有近似线性的时间复杂度.
多層快速多極子方法(MLFMM)可用來加速迭代求解由Maxwell方程組或Helmholtz方程導齣的積分方程,其複雜度理論上是O(NlogN),N為未知量箇數.MLFMM依賴于快速計算每層的轉移項,以及上聚和下推過程中的層間插值.本文引入計算類似N體問題的一維快速多極子方法(FMM1D).基于FMM1D的快速Lagrange插值算法可將轉移項的計算複雜度由O(N1.5)降低到O(N).運用FMM1D與FFT混閤的快速譜插值算法可將層間插值的計算複雜度由O(K2)降低到O(K log K),K為插值取樣點數.數值結果顯示瞭基于這兩種快速插值的MLFMM具有近似線性的時間複雜度.
다층쾌속다겁자방법(MLFMM)가용래가속질대구해유Maxwell방정조혹Helmholtz방정도출적적분방정,기복잡도이론상시O(NlogN),N위미지량개수.MLFMM의뢰우쾌속계산매층적전이항,이급상취화하추과정중적층간삽치.본문인입계산유사N체문제적일유쾌속다겁자방법(FMM1D).기우FMM1D적쾌속Lagrange삽치산법가장전이항적계산복잡도유O(N1.5)강저도O(N).운용FMM1D여FFT혼합적쾌속보삽치산법가장층간삽치적계산복잡도유O(K2)강저도O(K log K),K위삽치취양점수.수치결과현시료기우저량충쾌속삽치적MLFMM구유근사선성적시간복잡도.
