c++ - 为什么 Strassen 矩阵乘法比标准矩阵乘法慢得多？

Question

我用 C++、Python 和 Java 编写了矩阵乘法程序，并测试了它们对两个 2000 x 2000 矩阵相乘的速度(参见 post)。标准 ikj 实现 - 在 中- 拍摄:

• C++:15 秒(Source)
• Python:6 分 13 秒 (Source)

现在我已经实现了 Strassen algorithm for matrix multiplication - 位于 - 在 Python 和 C++ 中，就像在维基百科上一样。这些是我的时间:

• C++:45 分钟 (Source)
• Python:10 小时后被杀死 (Source)

为什么 Strassen 矩阵乘法比标准矩阵乘法慢很多？

---

想法:

• 一些缓存效果
• 实现:
  • 错误(生成的 2000 x 2000 矩阵是正确的)
  • null 乘法(对于 2000 x 2000 -> 2048 x 2048 应该没那么重要)

---

这尤其令人惊讶，因为它似乎与其他人的经历相矛盾:

• Why is my Strassen Matrix multiplier so fast?
• Matrix multiplication: Strassen vs. Standard - Strassen 对他来说也较慢，但至少在同一数量级。

---

编辑:在我的情况下，Strassen 矩阵乘法较慢的原因是:

• 我让它完全递归(参见 tam)
• 我有两个函数 strassen 和 strassenRecursive。如果需要，第一个将矩阵的大小调整为 2 的幂，并调用第二个。但是strassenRecursive并没有递归调用自己，而是strassen。

Answer 1

基本问题是您使用 strassen 实现递归到叶大小为 1。 Strassen 的算法具有更好的 Big O 复杂度，但常数确实在现实中很重要，这意味着实际上对于较小的问题规模，您最好使用标准的 n^3 矩阵乘法。

所以要大大改进你的程序而不是这样做:

if (tam == 1) {
        C[0][0] = A[0][0] * B[0][0];
        return;
    }

在此处使用 if (tam == LEAF_SIZE)//迭代解决方案。 LEAF_SIZE 应该是一个常量，您必须为给定的架构通过实验确定。根据架构的不同，它可能会更大或更小 - 有些架构中 strassen 的常数因子非常大，以至于对于合理的矩阵大小，它基本上总是比简单的 n^3 实现更差。这一切都取决于。