灵活预处理GPBiCG和并行BiCG方法

论文摘要

在科学工程计算中,许多大规模科学计算问题的数值模拟最终可以归结为大型稀疏线性代数方程组的求解。而代数方程组的求解时间往往在整体数值模拟时间中占有非常大的比重,以致成为整体数值模拟的瓶颈。因此设计高效的代数解法器是求解这类问题的关键所在,同时也是设计相关高性能软件的基石。目前,在给定Krylov子空间迭代算法前提下,有两种途径可以降低大型稀疏代数方程组的求解时间：一种是并行计算,另一种是使用预处理技术。本文主要研究了两项内容：一是利用FLAME框架重新推导BiCG方法,重排内积顺序,降低全局通信次数,提高方法的并行可扩展性；二是对于非对称线性方程组,给出了灵活预处理GPBiCG方法。首先,介绍如何利用FLAME(?)框架形式地推导Krylov子空间法。然后考虑BiCG方法,利用算法中向量序列的性质,即剩余向量的正交性和搜索方向的双共轭性,推导出几种不同但是数学上等价的BiCG算法,选出适合于在分布式存储处理机上并行计算的那些算法,进行了理论分析。并且用并行试验来表明新算法的确降低了全局通信时间,提高了算法的并行可扩展性。其次,我们给出可变预处理形式的GPBiCG方法,在方法的每一步中可使用不同的预处理子。特别地,可变预处理子的灵活性是可用任何一种迭代法得到。例如,标准的GPBiCG方法自身可以作为预处理了,其他的Krylov子空间法或是分裂迭代法也可以。对于可变预处理形式的GPBiCG方法,我们还进行了一些数值试验,这些算例表明了可变预处理迭代法的收敛性和健壮性。

论文目录

• 摘要
• Abstract
• 目录
• 第一章 绪论
• 1.1 研究背景
• 1.2 研究动态
• 1.2.1 软件开发背景
• 1.2.2 Krylov子空间迭代法的并行策略与研究现状
• 1.2.3 FLAME框架介绍
• 1.2.4 预处理技术
• 1.3 预备知识
• 1.3.1 基本概念
• 1.4 内容概要
• 第二章 形式推导和并行BiCG方法
• 2.1 基本理论
• 2.2 BiCG方法中系数矩阵D和U的计算
• 2.2.1 计算系数矩阵D
• 2.2.2 计算系数矩阵U
• 2.3 减少BiCG方法的同步点
• 2.4 性能分析
• 2.5 数值试验
• 2.6 本章小结
• 第三章 灵活预处理的GPBiCG算法
• 3.1 可变形式的GPBiCG方法
• 3.2 数值实验
• 3.3 小结
• 第四章 总结与展望
• 参考文献
• 简历
• 致谢