非对称线性系统的稀疏近似逆预条件子的研究

论文摘要

求解大型线性方程组是科学与工程计算中经常会遇到的问题，如何高效的求解大型线性方程组显得非常重要。随着方程组的规模越来越大，传统的迭代法已经很难取得良好的效果，在这种形势下，现代迭代法得到了极大的重视。随着分布式处理器越来越广泛的应用，可并行的预条件子成为一个非常有价值的研究方向。稀疏近似逆方法正是以其优良的并行性得到了很大的重视，在近二十年得到了很大的发展。稀疏近似逆法分成两种，一种基于Frobenius范数最小化，一种基于矩阵分解。本文分别对这两种方法进行了描述，列出了这两种方法中几个比较成功的算法，并对这些成功的算法进行了数值实验，对这些算法的适用范围和有效性等方面进行了对比和总结。本文提出了基于Frobenius范数最小化的更新稀疏模式的近似逆算法AIRP和近似逆的稀疏模式与A相同的PPA预条件子在并行机上的并行算法。然后通过数值实验对AIRP预处理前后的特征值分布和迭代曲线进行对比，可以看到AIRP算法是可行的，AIRP算法的健壮性强、精度高且并行性强。最后通过数值实验对预条件子AIRP和PPA进行对比，主要还是从特征值分布和迭代曲线两方面比较分析这两个算法的优缺点。得到的结论是AIRP预处理精度高，迭代速度快，但预处理时间要长一点；而PPA预处理精度上要差一点，但预处理时间较短，且需要的存储空间小。

论文目录

• 摘要
• ABSTRACT
• 第一章 引言
• 1.1 课题研究背景
• 1.2 迭代法基础知识
• 1.3 本文工作及创新
• 1.4 本文的内容和结构
• 第二章 稀疏近似逆预处理方法
• 2.1 稀疏近似逆法的发展背景
• 2.2 稀疏近似逆法的分类
• 2.2.1 基于Frobenius 范数最小化的稀疏近似逆法
• 2.2.2 基于矩阵分解的稀疏近似逆法
• 2.3 数值实验
• 2.3.1 系数矩阵 A为对称的正定矩阵时的数值实验
• 2.3.2 系数矩阵 A为非对称正定矩阵时的数值实验
• 2.4 本章总结
• 第三章 更新稀疏模式的近似逆算法
• 3.1 构造更新稀疏模式的近似逆算法
• 3.2 M 的稀疏模式与 A相同的近似逆算法
• 3.2.1 构造M 的稀疏模式与 A相同的近似逆算法
• 3.2.2 PPA算法的并行方法
• 3.3 关于M 的理论性分析
• 3.4 数值实验
• 3.4.1 AIRP预处理前后的特征值分布和迭代曲线
• 3.4.2 算法AIRP与PPA的对比
• 3.5 本章总结
• 第四章 总结和展望
• 致谢
• 参考文献