论文部分内容阅读
寻求大型稀疏线性方程组的高效并行解法是当前大规模科学计算中亟待解决的热点问题。Krylov子空间算法是求解大型稀疏线性方程组最流行和最有效的迭代方法之一，其并行计算主要考虑矩阵向量乘和内积计算。目前通过适当编码，矩阵向量乘在并行计算时不会造成严重性能降低的通信问题。但内积计算并非如此，由于内积计算需要全局通信，在分布式并行计算环境下其成为高效并行计算的瓶颈。
ORTHOMIN(m)算法和GCR(k)算法是两种Krylov子空间算法，为减少两算法内积计算引起的全局通信以提高并行性能，本文以油藏数值模拟问题为应用背景分别对两算法做了如下工作：
首先利用ORTHOMIN(m)算法的固有性质改变其计算次序，给出了该算法的改进形式，其次对算法进行了并行设计、理论分析，最后通过求解油藏数值模拟问题给出数值实验。同ORTHOMIN(m)算法相比，改进算法与ORTHOMIN(m)算法具有相同的收敛性，在分布式并行计算环境下进行并行计算时改进算法用连续内积计算代替了ORTHOMIN(m)算法分离的内积计算，消除了ORTHOMIN(m)算法两次内积计算的数据相关性，使同步开销次数减少为ORTHOMIN(m)算法的一半进而加大了计算时间相对通信时间的比重，提高了并行效率。理论分析表明当处理机台数较多时改进算法比ORTHOMIN(m)算法的并行计算时间要快，有更好的加速比及可扩展性。数值实验结果也表明改进算法的并行性能要优于ORTHOMIN(m)算法，更利于油藏数值模拟问题的并行求解。
对于GCR(k)算法，利用同样的方法给出了该算法的改进形式，并给出算法的并行设计、理论分析，且通过求解油藏数值模拟问题给出数值实验。与ORTHOMIN(m)算法类似，改进算法与GCR(k)算法具有相同的收敛性，在分布式并行计算环境下进行并行计算时改进算法使同步开销次数减少为GCR(k)算法的一半，提高了并行效率。理论分析同样表明当处理机台数较多时改进算法比GCR(k)算法的并行计算时间要快，有更好的加速比及可扩展性。数值实验结果也同样表明改进算法的并行性能要优于GCR(k)算法，更利于油藏数值模拟问题的并行求解。