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

基于块Broyden方法的并行预处理技术的研究

作　者: 丁秀梅
导　师: 杨庚
学　校: 南京邮电大学
专　业: 计算机应用技术
关键词: 预处理技术矩阵对非线性方程组非线性系统 Broyden 迭代算法迭代次数并行计算技术构造方法并行化技术近似逆矩阵解方程组存储需求条件数分块研究生学位论文算法实现时间复杂度算法收敛性子区域
分类号: O241.7
类　型: 硕士论文
年　份: 2011年
下　载: 9次
引　用: 0次
阅　读: 论文下载

内容摘要

高性能计算在科学研究和工程应用中扮演着日益重要的角色,其面临的基本问题之一是超大规模非线性方程组的数值求解。非线性系统维数的巨大,常常导致算法不仅对内存有巨大的需求,而且收敛速度往往很慢,可靠性差。这些因素常使算法无法真正应用到工程实际中,因此必须寻求高效的能够实际应用的数值方法。目前,人们通常采用并行计算技术,以提高求解问题的规模,加快求解问题的速度。本文的目标就是基于块Broyden方法,建立并行求解非线性方程组迭代算法的预处理方法,从而达到提高算法收敛性的目的,并为今后的并行化、整体化的预处理方法的研究奠定理论基础。本文首先描述了求解非线性方程组的几种经典迭代算法(包括牛顿法、拟牛顿法等),显示了块Broyden方法的优势。回顾了预处理技术的发展历史,分析了预处理矩阵的基本构造要求,讨论了六种不同的预处理技术。然后,将块Broyden方法与各种预处理技术相结合形成不同的BBP算法,并从理论上分析了各种算法在串行和并行下求解大规模非线性系统方面的时间复杂度和存储需求,进而推导出性能比较的定量公式。最后,将BBP算法运用到计算物理经典的Bratu问题的数值求解中,得到了详尽的实验数据,并依据理论分析中给出的公式,对各种求解方法的性能进行了分析比较。试验数据表明,结合了预处理技术的块Broyden算法具有更好的求解性能,可适用于大规模科学与工程的高性能计算。

全文目录

摘要  4-5
Abstract  5-7
第一章引言  7-22
  1.1 论文的研究背景及意义  7-9
  1.2 研究现状  9-17
    1.2.1 矩阵分裂型预条件  10-11
    1.2.2 不完全分解型预条件  11-13
    1.2.3 稀疏近似逆型预条件  13-14
    1.2.4 多层型预条件  14-15
    1.2.5 多项式型预条件  15
    1.2.6 预处理矩阵中的并行处理技术  15-17
  1.3 基本术语和基本概念  17-20
  1.4 论文的主要内容及其组织结构  20-22
第二章非线性方程组求解的迭代算法  22-27
  2.1 非线性方程组求解的迭代算法概述  22-23
  2.2 牛顿法  23-24
  2.3 拟牛顿法  24-25
  2.4 块Broyden方法  25-27
第三章预处理技术  27-33
  3.1 预处理技术概述  27-29
    3.1.1 预处理技术发展历史  27-28
    3.1.2 预处理矩阵的构造格式和要求  28-29
  3.2 几种常见的预处理技术  29-32
    3.2.1 Jacobi技术  29-30
    3.2.2 Block Jacobi技术  30
    3.2.3 SOR技术和SSOR技术  30-31
    3.2.4 ILU(0)技术  31-32
  3.3 AILU(0)预处理技术  32-33
第四章基于块Broyden方法的并行预处理技术  33-44
  4.1 算法描述  33-34
  4.2 算法实现  34-35
  4.3 算法的性能分析  35-44
    4.3.1 执行时间分析  35-39
    4.3.2 预处理矩阵的构造代价  39-42
    4.3.3 存储需求分析  42-44
第五章数值算例  44-54
  5.1 问题描述及离散化  44-45
  5.2 低维情况下各种BBP算法的性能  45-49
  5.3 高维情况下各种BBP算法的性能  49-54
第六章总结与未来的工作  54-57
  6.1 总结  54-55
  6.2 未来的工作  55-57
致谢  57-58
参考文献  58-60

基于块Broyden方法的并行预处理技术的研究

内容摘要

全文目录

相似论文