三角稀疏矩阵的层次调度

计算科学 线性代数 并行计算 稀疏矩阵
2021-12-05 17:19:17

假设有一个三角形稀疏矩阵并想解决Lx=b在哪里bL是已知的。这可以通过使用前向替换轻松完成L是一个下三角矩阵。前向替换是高度连续的,难以并行实现。我已经阅读了一些关于级别调度的文章,其中L被重新排序,以便出现可以并行解决的不同级别。一个很好的参考似乎是 Saad 的书,其中还解释了使用级别调度的前向替换。

但我并没有真正了解如何执行级别调度以及向量q充满。有人可以提供一个例子吗?

1个回答

您可以尝试在 L 和 U 中发现并行性,但更好的方法是重新排序原始矩阵。Luby & Jones/Plassman 描述了这种方案:您可以并行生成多种颜色,然后在解决方案中,每种颜色的所有处理器都同时处于活动状态。