精品文档---下载后可任意编辑GMRES 并行算法讨论中期报告介绍本文是 GMRES 并行算法讨论的中期报告，主要介绍了 GMRES 算法的基本思想和串行算法的实现方法，以及目前已完成的并行 GMRES算法的讨论进展
GMRES 算法简介GMRES（Generalized Minimal Residual）算法是一种求解稀疏线性方程组的迭代算法
它的基本思想是通过在 Krylov 子空间中寻找能够最小化残差的向量来为线性方程组求解近似解
因为 Krylov 子空间的维数随着迭代次数的增加而增加，因此 GMRES 算法通常需要在每次迭代中求解一个小规模的最小二乘问题
然而，这个最小二乘问题的规模可能会随着迭代次数的增加而增加，因此 GMRES 算法的计算复杂度通常比其他迭代算法高
尽管如此，GMRES 算法具有很好的收敛性和稳定性，因此在实际求解大规模稀疏线性方程组时仍然广泛使用
串行 GMRES 算法的实现GMRES 算法的串行实现有很多变种，但它们都有一些共同的特点
首先，它们都需要利用稀疏矩阵-向量乘积的性质来计算 Krylov 子空间中的向量
其次，它们都需要在 Krylov 子空间中求解最小二乘问题
这一步通常可以用 QR 分解或者奇异值分解（SVD）来完成
最后，串行GMRES 算法还需要选择一个合适的终止条件来确定算法的迭代次数
并行 GMRES 算法的讨论进展由于 GMRES 算法的计算复杂度较高，因此并行 GMRES 算法的讨论备受关注
目前已有很多并行 GMRES 算法被提出，它们的并行方式可以分为两类：基于数据并行的算法和基于任务并行的算法
基于数据并行的算法基于数据并行的算法是将稀疏矩阵和向量按行或者列划分成若干个块，并将这些块分配给不同的处理器进行并行计算
这样做的好处是相对简单，适用于稀疏矩阵-向量乘积的计算
但是，它的缺点是容易出现负载不平衡的情
