当前位置: 代码迷 >> 综合 >> 《A synchronization-free algorithm for parallel sparse triangular solves》读后总结
  详细解决方案

《A synchronization-free algorithm for parallel sparse triangular solves》读后总结

热度:5   发布时间:2023-12-14 06:09:44.0

正式读研之后看的第一篇文献。本着“只有记录下来的才是自己的”这一原则,记录一下。

论文提出的方法用来解决多元一次方程组中系数矩阵为下三角的情况(Lx = b中,L为下三角矩阵)

A示意图

如上图所示,对应的方程组如下“

a(0,0)x0 = b0

a(1,1)x1 = b1

a(2,1)x1 + a(2,2)x2 = b2

...

a(4,1)x1+a(4,2)x2+a(4,3)x3+a(4,4)x4 = b4

...

可以看到x0和x1可以直接得解,而x2必须等待x1计算完成之后才可以计算,同理x4必须等待x1,x2,x3计算完成以后才能开始计算。如果用x->y表示y必须等待x计算完成之后才能开始计算,则可得下图

 对这张解的顺序图进行拓扑排序,对不同层进行level标记,则可得下图