1、大规模稀疏矩阵大规模稀疏矩阵并行计算并行计算李修宇QQ： 295553381* 1主流求解方法主流求解方法 直接法o GAUSS消去法o 波前法o 多波前法 迭代法o 经典迭代法 Jacobi、 SOR、 SSORo 投影方法 CG、 GMRESo 预处理技术 不完全分解预处理条件o 代数多重网格技术*大规模稀疏矩阵并行计算 2矩阵性质对求解的影响矩阵性质对求解的影响性质 影响*大规模稀疏矩阵并行计算 3 非零元的分布o 带状分布o 按块分布o 正定性 对称性 矩阵的存储方式 求解方法的选择 求解速度 直接法直接法 矩阵图重排：一般分为两大类，带宽缩减算法（也常称为外形缩减）和区域分解算法，应
2、用较多的带宽缩减算法CM， RCM， GPS， Rosen算法。一般建议多重方法结合使用：全局方法的全局平衡性、局部方法的局部最优特性。 符号分解：确定非零元结构以及相应的消元索引，以便在实际数值分解前确定所需存储资源大小，避免数值分解中动态分配存储空间和复杂的索引策略。 构建消去树 (elimination tree)：确定分解节点之间的分解依赖，即确定分解的顺序并构成并行分解的层次结构。*大规模稀疏矩阵并行计算 4直接法直接法 数值分解：利用符号分解得到的非零元结构和索引沿消去树路径进行分解。 回代求解：包括前向（ forward）和后向（ backward）回代，可先构建消去依赖树或顶点
3、着色技术实现并行回代求解。 在有限元领域应用最广的直接求解方法常使用带宽缩减或多区域分解的多波前法（ multifrontal）。*大规模稀疏矩阵并行计算 5对称正定矩阵的求解对称正定矩阵的求解*大规模稀疏矩阵并行计算 6对称矩阵的不完全分解对称矩阵的不完全分解*大规模稀疏矩阵并行计算 7代数多重网格法代数多重网格法 V-Cycle AMG（ V循环多重网格法） W-Cycle AMG（ W循环多重网格法） FMG（完全多重网格法：嵌套网格与 V循环或者 W循环结合）*大规模稀疏矩阵并行计算 8代数多重网格法代数多重网格法*大规模稀疏矩阵并行计算 9代数多重网格法代数多重网格法 在粗网格上对残差方程进行求解（可用迭代法或直接解法）。 延拓或插值（ interpolation）：将细网格节点上的值通过分片插值延拓到细网格节点上。 通过光滑的残差对解进行修正。 后光滑（ post-smooth），类似于前光滑。*大规模稀疏矩阵并行计算 10
