适合分布式并行计算改进的GCRS算法研究

Efficient numerical solutions of linear systems play a key role in alrge-scale scientific computing and engineering disciplines. However, the Krylov subspace methods enforce bottleneck, i.e., the global communication induced by inner product computations, when used in large-scale parallel computing. The research will considers mainly how to reduce global communication, design generalized conjugate residual squared(GCRS) algorithm and the improved algorithm suitable for distributed parallel computing. First, the research will design Krylov subspace GCRS algorithm and improved algorithm, then derive and analyze theoretically the corresponding improved algorithm suitable for distributed parallel computing, improved algorithm reduces mainly the global synchronization points, by changing the computation sequence in the algorithm and all inner products per iteration are independent, and communication time required for inner product can be overlapped with useful computation, Finally, we analyze the convergence, the complexity, the parallelism and the efficiency of the improved algorithms, write some programs and make numerical comparison. Moreover, the proposed efficient algorithms compose numerical stability and parallel algorithms design elements and provide some theoretical basis and application value for the solution of practical problems.

线性代数方程组的高效数值求解问题是近年来大规模科学计算和工程技术中研究的热点之一。当在大规模并行计算中使用Krylov子空间迭代法时，将面临瓶颈问题：全局通讯和并行预条件子的有效性。本研究课题主要考虑如何降低全局通讯，设计广义平方共轭残差算法及适合分布式并行计算改进的算法。本研究课题首先设计Krylov子空间GCRS迭代算法和改进的GCRS迭代算法，然后推导和理论分析相应的适合分布式并行计算改进的算法，改进的算法主要降低整体同步化点，通过算法的重构，使得所有内积计算及矩阵向量乘积是独立的，没有数据相关性，可进行计算与通讯的重叠，最后分析改进算法的收敛性、复杂度、并行性和等效率等，并编写程序进行数值比较。同时，提出的高效迭代算法组合数值稳定性和并行算法设计的要素，对实际问题的求解提供了一定的理论依据和应用价值。

本研究项目提出了一种适合于分布式并行环境, 求解大型稀疏非对称线性方程组改进的广义平方共轭残差(Generalized Conjugate Residual Squared)算法, 简记为IGCRS (Improved Generalized Conjugate Residual Squared)算法. 通过算法重构, IGCRS方法比GCRS方法所需要的两个全局同步化点降低到了一个, 并且所有内积计算以及矩阵向量乘积是独立的, 没有数据相关性, 可进行计算与通信的重叠. 本研究项目提出的方法组合了数值稳定性与并行算法设计的要素, 代价仅是增加了一点计算量. 性能分析表明IGCRS方法比GCRS方法具有更好的并行性和可扩展性. 数值试验表明IGCRS方法相比于GCRS方法, 利用不同的处理器台数并行通讯性能改进平均趋向于52.19%, 同时还比较了BiCR, GCRS2, BiCG和CGS的收敛速度. 本研究项目提出的IGCRS迭代算法组合数值稳定性和并行算法设计的要素, 对实际数值模拟问题的求解提供了一定的理论依据和应用价值.