并行 Gram-Schmidt 算法

计算科学 线性代数 并行计算
2021-12-20 06:03:10

我听说经典的 Gram-Schmidt 比修改后的 Gram-Schmidt 更适合并行化。显然原因与我不熟悉的“2级BLAS”有关。此外,在对这个问题的评论中,@Jed Brown 谈到了左眼和右眼的 Gram-Schmidt,我没有找到参考。

Gram-Schmidt 算法在实践中是如何并行化的,并行化的效果如何

1个回答

首先,Blas(基本线性代数子程序)是一组高度优化的低级函数,执行标准线性代数运算,如缩放、点积和矩阵乘法。因此,希望利用这些功能来获得最佳性能。

修改后的 Gram-Schmidt(MGS) 相对于经典 Gram-Schmidt 的主要优势在于它通过重新排列操作顺序提供了更好的稳定性。因此,它经常在实践中使用。不幸的是,MGS 不能由 BLAS 例程表示,并且在并行实现时需要额外的通信。

实际上,如果您拥有显卡,您将求助于一些并行编程语言,例如 OpenMP 或 CUDA。在文章http://www.drdobbs.com/go-parallel/article/print?articleId=240006334&siteSectionName=中,他们提到使用 OpenMP 的串行实现速度提高了 3 倍,使用 OpenACC 时几乎提高了 9 倍。大小103×103. 您还可以查看http://link.springer.com/article/10.1140/epjst/e2012-01638-7#page-1以比较 GPU 和 CPU 实现。