迭代法中基本操作的并行算法.ppt

《迭代法中基本操作的并行算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、迭代法中基本操作的并行算法内积的并行计算非零元结构对应于网格的矩阵与向量相乘一般稀疏矩阵与稠密向量的并行乘法将一次迭代内所有操作一起并行计算时的考虑2021/8/271内积的并行计算假设要计算(x,y)，其中则有例子：P0x0~99y0~99P1x100~199y100~199P2x200~299y200~299P3x300~399y300~3992021/8/272非零元结构对应于网格的矩阵与向量相乘简单的一维分布2021/8/273非零元结构对应于网格的矩阵与向量相乘(续)二维分布2021/8/274非零元结构对应于网格的矩阵与向量相乘(续)使负载更平衡的

2、一种分布形式2021/8/275一般稀疏矩阵与稠密向量的并行乘法一般稀疏矩阵的非零元结构对应于一个有向图，矩阵与向量进行乘法时，yk的计算所依赖的x分量对应于图中结点k的出边对应于yk的计算量完全由k的出边数量决定在计算y＝Ax时，寻找使负载平衡且通信量最少的矩阵行分布就等价于对图G进行分割，使各子图内所有顶点的出边总数大致相当，而所有子图间的边数之和最少2021/8/276一般稀疏矩阵与稠密向量的并行乘法(续)例如，对非零元结构对应于下图的稀疏矩阵，在两个进程上并行计算时，红线对应的分布更好2021/8/277将一次迭代内所有操作一起并行计算时的考虑在内积并

3、行计算时，为平衡负载，最好将向量分量个数平均分布到各个进程，而向量分量的分布与矩阵的行分布相对应，这对应于对图进行分割时，使得各子图中的结点数相等在稀疏矩阵与向量并行乘时，为平衡负载，应使得各子图内所有顶点的出边总数大致相当这两个目标有时是相互冲突的2021/8/278