加载中…
个人资料
多物理场仿真
多物理场仿真
  • 博客等级:
  • 博客积分:0
  • 博客访问:204,426
  • 关注人气:267
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

FEM之杂谈(2)---快速多级子算法介绍

(2015-04-18 09:20:45)
标签:

快速多极子

算法

线性方程组

fmm

杂谈

分类: 求解器开发
FMM(Fast Multipole Method)快速多级子算法被美国工业与应用数学学会命名为20世纪十大算法之一(http://www.uta.edu/faculty/rcli/TopTen/topten.pdf)

FEMFMM本来不太相干,为了方便放在FEM杂谈中。

通常有限元方法最后的线性方程组的系数矩阵为对称稀疏矩阵,因此编程求解计算量和内存消耗都与单元数量成线性比例关系。但其他求解偏微分方程的方法比如矩量法,边界元法等最终形成的线性方程组系数为非对称非稀疏矩阵,常规计算方法所需的存储该系数矩阵要O(N*N),计算量达O(N*N*N),因此当单元增加时,计算量和内存消耗急剧增加,从而限制了很多数值方法在实际工程中的运用。FMM的出现解决了这个问题,使得计算量和内存消耗与单元的数量也达到了线性关系。

快速多级算法的计算量与求解问题的规模虽然呈线性关系,但是这个线性斜率很大,导致快速多级算法的优势只有在大规模问题上才能体现出来。在常用的FMM基础上出现很多改进算法,多层快速多级子算法,和其它算法的混合算法。

开源的FMM资源:
ExaFMM(http://www.bu.edu/exafmm/)
Puma-EM(http://sourceforge.net/projects/puma-em/)

0

阅读 收藏 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有