大规模稀疏矩阵并行计算.ppt.ppt

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