algorithm - 交叉点：Strassen 算法

Question

就效率而言，施特拉森算法应该停止递归并应用乘法的最佳交叉点是什么？

我知道这与具体的实现和硬件密切相关，但是对于一般情况，应该有某种指导方针或某人的一些实验结果。

在网上搜索了一下，问一些他们倾向于认为的人

n = 64; 

或者

 n = 32;

任何人都可以验证/拒绝这些结果吗？

Answer 1

这应该在每台机器的基础上进行调整（有点像 ATLAS 所做的）。这种优化对于相当大的矩阵是有回报的：如果你自己编写代码，并将其与例如。供应商 BLAS 实现，那么你会发现一个相当大的 n。

Strassen 算法的内存要求也是需要权衡的。

Answer 2

在我的双核 2.66 Mac Pro 上，使用 [我的实现][1]，交叉点小到 n = 16。事实上，我的实现比大型矩阵的传统算法快得多——我不知道为什么—— - 我认为它对缓存更友好，因为它专注于较小的本地化数据。事实上，我即将发布一个关于此的问题。

http://ezekiel.vancouver.wsu.edu/~cs330/lectures/linear_algebra/mm/mm.c

Answer 3

经过大量测试，我得出结论，至少对于我的处理器而言，施特拉森算法的最佳交叉点是n = 128.

我的处理器是：英特尔酷睿 i5-430M。此外，有趣的是，对于 4 线程 CPU，我的实现numberOfProcesses = 8比numberOfProcesses = 4. 我不知道这是如何或为什么发生的。我猜想由于通过渠道进行更多的沟通，它会产生更大的开销，并且由于它们不能同时工作，所以肯定会慢一些。显然我错了。如果有人可以解释这个顺便说一句，请写一行，仅供记录。

谢谢。