反向替换不是并行完成这一事实并不重要,因为与前向消除相比,当 N 很大时,它使用的计算机时间可以忽略不计。
这是本书(第 204 页)在讨论使用高斯消元法实现线性系统的并行解决方案时的引文。我怀疑在实践中人们确实并行化了反向替换,并且一个简短的谷歌搜索表明存在这样的算法。所以问题是:
- 什么时候并行反向替换是合理的,什么时候不合理?
- 到目前为止,最有效的并行反向替换算法是什么?
反向替换不是并行完成这一事实并不重要,因为与前向消除相比,当 N 很大时,它使用的计算机时间可以忽略不计。
这是本书(第 204 页)在讨论使用高斯消元法实现线性系统的并行解决方案时的引文。我怀疑在实践中人们确实并行化了反向替换,并且一个简短的谷歌搜索表明存在这样的算法。所以问题是:
你是对的,如果只有右手边可以同时求解,然后三角形求解不是很可扩展。但是,如果有过程和右手边,则存在可扩展算法,因为每个右手边都是独立的。
我相信当前使用单个右手边求解平行三角形的黄金标准是Joshi 等人的这篇论文。. 快速可扩展的三角求解对许多算法都很重要,尤其是在 Krylov 算法中嵌入近似分解时,因为每次迭代都需要求解一个或多个三角系统。一种有效的技巧是显式反转因子的三角矩阵,以便三角解成为三角矩阵-向量乘法(参见选择性反转)。