大规模稀疏矩阵并行求解

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