学位论文 > 优秀研究生学位论文题录展示

并行GPBiCG（m，l）算法与预处理技术

作　者: 朱圣鑫
导　师: 刘兴平；谷同祥
学　校: 中国工程物理研究院
专　业: 计算数学
关键词: 并行算法 Krylov子空间迭代法 预处理技术 模板消元法 非负矩阵反问题
分类号: O241.6
类　型: 硕士论文
年　份: 2010年
下　载: 40次
引　用: 0次
阅　读: 论文下载
 

内容摘要


许多大规模科学计算问题的数值模拟最终归结为大型稀疏线性或非线性代数方程组的求解.而代数方程组的求解时间往往在整体数值模拟时间中占有非常大的比重,以致成为整体数值模拟的瓶颈.因此,设计高效的代数解法器是求解这类问题的关键所在,同时也是设计相关高性能软件的基石.目前,在给定Krylov子空间迭代方法的前提下,有两种途径可以降低大型稀疏代数方程组的求解时间.一种是并行计算,另一种是使用预处理技术.本文主要研究了三项内容：一种并行Krylov子空间算法的设计与分析；一种新的基于模板消元的预处理技术和在研究预处理理论中遇到的一类特征值反问题.首先,针对Krylov子空间迭代法并行计算的瓶颈问题：全局通信,以文献中最近出现的GPBiCG(m,l)方法为例来说明如何设计并行Krylov子空间方法.设计思想是将原方法中的每次迭代需要的三个内积同步点降低到一个.我们称新方法为改进的GPBiCG(m,l)(简称为IGPBiCG(m,l))方法.本文理论上证明了IGPBiCG(m,l)方法的并行可扩展性比原方法好3倍以上,证明了当问题的规模足够大时,在相同条件下IGPBiCG(m,l)方法的求解时间相比原方法节省趋向于66%.数值试验得到了与理论分析相吻合的结果.另外,尽管GPBiCG(1,0)方法数学上等价于BiCGSTAB,但是数值试验表明IGPBiCG(1,0)方法的收敛性比[92]中的IBiCGSTAB方法好.其次,我们提出了一种基于模板消元的新的预处理技术.文[96]提出了基于数学模板(Stencil)消元方法来构造并行差分格式,我们将这种方法发展为一种模板消元预处理技术.对于由五点差分格式或七点差分格式离散二维或三维偏微分方程得到的,经过对角尺度化的大型稀疏线性方程组,我们证明了使用模板消元预处理技术后,利用Krylov子空间迭代法求解预处理线性方程组的速度是求解原方程组速度的两倍.这种预处理技术易于实施,且容易和其它现有的预处理技术结合使用.数值试验结果表明,将其与ILU(0)等预处理方法结合使用,能明显地加快Krylov子空间迭代法的收敛速度.另外,基于数学模板消元技术,我们提出了具有良好并行性的代数模板消元法.讨论了如何利用代数模板消元法求矩阵的逆,并且分析了这种方法计算复杂度.最后,为了保持特殊矩阵之逆的一些性质,我们提出了一种简单且实用的算法,以求解非负矩阵和M矩阵的特征值反问题.给出了算法的稳定性、敏感性、计算量分析以及非负矩阵反问题与M矩阵反问题可解的充分条件和必要条件；将新算法发展成为一种多层自适应算法,并以大量的算例验证了算法的有效性.

全文目录


摘要  5-7
Abstract  7-14
第一章 绪论  14-28
  1.1 研究背景  14-16
  1.2 研究动态  16-21
    1.2.1 Krylov子空间迭代法的并行策略与研究现状  16-18
    1.2.2 预处理技术与理论的研究现状  18-20
    1.2.3 非负矩阵反问题及其研究现状  20-21
  1.3 预备知识  21-26
    1.3.1 基本概念  22-24
    1.3.2 基本计算量  24-25
    1.3.3 构造预处理子的一般原则  25-26
  1.4 内容概要  26-28
第二章 并行GPBiCG(m,l)算法  28-52
  2.1 算法设计  28-34
    2.1.1 GPBiCG(m,l)算法  28-31
    2.1.2 数据关系分析  31-32
    2.1.3 并行改进的GPBiCG(m,l)算法  32-34
    2.1.4 几种算法的关系  34
  2.2 性能分析  34-45
    2.2.1 性能评价模型  35-37
    2.2.2 可扩展性分析  37-42
    2.2.3 收敛性能分析  42-45
  2.3 数值试验  45-48
  2.4 本章小节  48-52
第三章 模板消元预处理技术  52-70
  3.1 模板消元法  52-55
    3.1.1 数学模板消元法思想与示意图  52-53
    3.1.2 数学模板消元法的代数描述  53-55
  3.2 模板消元与预处理技术  55-60
    3.2.1 模板消元预处理方法  55-56
    3.2.2 模板消元预处理法的收敛性能  56-60
  3.3 代数模板消元法  60-64
    3.3.1 算法描述  60-63
    3.3.2 算法复杂性分析  63-64
  3.4 试验设计  64-67
  3.5 本章小结  67-70
第四章 特征值反问题  70-88
  4.1 几个引理  71-75
  4.2 算法设计与存在性定理  75-76
  4.3 算法分析  76-79
    4.3.1 敏感性分析  76-78
    4.3.2 更一般的结果  78-79
  4.4 SNIEP与逆M-矩阵可解的条件  79-81
  4.5 多层自适应HROU算法  81-86
  4.6 本章小结  86-88
第五章 总结与展望  88-90
参考文献  90-100
发表文章目录  100-101
简历  101-102
致谢  102

相似论文

  1. 频繁图结构并行挖掘算法的研究与实现,TP311.13
  2. 基于并行算法的模糊综合评价模型的设计与应用,TP18
  3. 基于视觉反馈与行为记忆的GPU并行蚁群算法,TP301.6
  4. GPU加速的仿射算术在几何设计中的应用研究,TP391.41
  5. 基于GPU的H.264到AVS视频转码并行设计,TN919.81
  6. H.264并行编码算法设计及其在GPU上的实现,TP391.41
  7. 基于ADSPTS201S的并行信号处理系统的设计与实现,TN957.51
  8. 基于小波变换的图像压缩并行算法研究,TP391.41
  9. 基于GPU的并行蚁群优化算法的研究与实现,TP301.6
  10. 基于MapReduce的聚类算法的并行化研究,TP311.13
  11. 面向星载计算机的容错并行算法研究与实现,TP302.8
  12. 激光能量沉积光路追踪法及其并行化,TN241
  13. 微可压缩模型预处理求解方法研究,O35
  14. 基于LBM的两相流数值模拟及其并行算法的实现,O359
  15. 基于树形计算结构的电力系统潮流并行算法研究,TM744
  16. RFID复杂应用中数据预处理技术的研究,TP391.44
  17. D-TIN并行构建方法及其在地图综合中的应用研究,P283
  18. 电大导体目标宽带RCS快速计算的关键技术研究,TN011
  19. 基于块Broyden方法的并行预处理技术的研究,O241.7
  20. 大规模稀疏线性方程组的预条件迭代法的研究,O241.6
  21. 图像匹配的并行算法研究,TP301.6

中图分类: > 数理科学和化学 > 数学 > 计算数学 > 数值分析 > 线性代数的计算方法
© 2012 www.xueweilunwen.com