为什么施特拉森矩阵乘法比标准矩阵乘法慢得多？

I have written programs in C++, Python and Java for matrix multiplication and tested their speed for multiplying two 2000 x 2000 matrices (see post http://martin-thoma.com/matrix-multiplication-python-java-cpp/). The standard ikj-implentation - which is in - took:

• C++： 15 秒（Source https://github.com/MartinThoma/matrix-multiplication/blob/master/C++/ikj-algorithm.cpp)
• Python：6分13秒（Source https://github.com/MartinThoma/matrix-multiplication/blob/master/Python/psyco-ikj-multiplication.py)

Now I have implemented the Strassen algorithm for matrix multiplication http://en.wikipedia.org/wiki/Strassen_algorithm#Source_code_of_the_Strassen_algorithm_in_C_language - which is in - in Python and C++ as it was on wikipedia. These are the times I've got:

• C++： 45分钟 （Source https://github.com/MartinThoma/matrix-multiplication/blob/master/C++/strassen.cpp)
• Python：10小时后被杀死（Source https://github.com/MartinThoma/matrix-multiplication/blob/master/Python/strassen-algorithm.py)

为什么施特拉森矩阵乘法比标准矩阵乘法慢得多？

• 一些缓存效果
• Implementation:
  • 错误（生成的 2000 x 2000 矩阵是正确的）
  • 空乘（对于 2000 x 2000 -> 2048 x 2048 来说应该不那么重要）

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

• 为什么我的 Strassen 矩阵乘法器如此快？ https://stackoverflow.com/q/7827737/562769
• 矩阵乘法：Strassen 与标准 https://stackoverflow.com/q/4304600/562769- 施特拉森对他来说也慢一些，但至少是在同一个数量级上。

编辑：在我的例子中施特拉森矩阵乘法较慢的原因是：

• 我使它完全递归（参见 tam）
• 我有两个功能strassen and strassenRecursive。如果需要，第一个将矩阵大小调整为 2 的幂，并调用第二个。但strassenRecursive没有递归调用自身，但是strassen.

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

因此，要大大改进您的程序，而不是这样做：

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

use if (tam == LEAF_SIZE) // iterative solution here. LEAF_SIZE应该是一个常数，您必须针对给定的架构通过实验确定该常数。根据架构的不同，它可能更大或更小——在某些架构中，strassen 的常数因子太大，以至于对于合理的矩阵大小来说，它基本上总是比更简单的 n^3 实现更糟糕。这一切都取决于。