Strassen 与 Winograd 矩阵乘法算法的速度和准确性

计算科学 矩阵
2021-11-25 12:30:31

我正在做的工作需要尽可能快的矩阵乘法,只是想与这个社区再次确认 Strassen 的 MM 算法的 Winograd 变体是最快的实用算法(所以没有 Coppersmith-Winograd)算法。

我在每个 MM 之前、之间和之后对数据进行了大量处理,以至于使用 Mathematica 或 Matlab 会成为障碍。

另外,我很好奇是否有人对常规 Strassen vs Winograd 变体中的错误有一个好主意?在“利用 SMP 系统的矩阵计算内核中的并行性”D'Alberto 等人。简单地提到 Strassen 更准确,但这似乎违反直觉,因为 Winograd 总体上的操作较少。

编辑:我们使用的矩阵大小最大为 2^16 x 2^16 ~ 40 亿个双精度数,因此亚三次算法肯定比简单算法更快。

编辑 2:关于 Strassen vs Winograd 的准确性,如果有人感兴趣的话。在“数值算法的准确性和稳定性”中,Higham 对这两种算法的误差进行了深入分析,并表明 Strassen 相对于矩阵大小而言误差增长较慢。另外值得注意的是,Strassen 对于所有正条目的矩阵更容易出错(自相矛盾)。

谢谢

0个回答
没有发现任何回复~