并行反向替换的实用性

计算科学 线性代数 并行计算
2021-12-13 20:35:18

反向替换不是并行完成这一事实并不重要,因为与前向消除相比,当 N 很大时,它使用的计算机时间可以忽略不计。

这是本书(第 204 页)在讨论使用高斯消元法实现线性系统的并行解决方案时的引文。我怀疑在实践中人们确实并行化了反向替换,并且一个简短的谷歌搜索表明存在这样的算法。所以问题是:

  1. 什么时候并行反向替换是合理的,什么时候不合理?
  2. 到目前为止,最有效的并行反向替换算法是什么?
1个回答

你是对的,如果只有O(1)右手边可以同时求解,然后三角形求解不是很可扩展。但是,如果有p过程和O(p)右手边,则存在可扩展算法,因为每个右手边都是独立的。

我相信当前使用单个右手边求解平行三角形的黄金标准是Joshi 等人的这篇论文。. 快速可扩展的三角求解对许多算法都很重要,尤其是在 Krylov 算法中嵌入近似分解时,因为每次迭代都需要求解一个或多个三角系统。一种有效的技巧是显式反转因子的三角矩阵,以便三角解成为三角矩阵-向量乘法(参见选择性反转)。