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

Question

我已经写方案C++,Python和Java的矩阵乘法和测试他们的速度有两个2000×2000矩阵(见相乘后).标准的ikj-implementntation - 在 - 拿:

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

现在我已经实现了用于矩阵乘法的Strassen算法 - 它在 - 在维基百科上的Python和C++中.这些是我的时代:

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

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

---

思路:

• 一些缓存效果
• 执行:
  • 错误(生成的2000 x 2000矩阵是正确的)
  • null-multiplication(对于2000 x 2000 - > 2048 x 2048不应该那么重要)

---

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

• 为什么我的Strassen Matrix倍增器如此之快？
• 矩阵乘法: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) // iterative solution here.LEAF_SIZE应该是一个常数,你必须通过实验确定你的给定架构.根据架构,它可能更大或更小 - 有一些架构,其中strassen的常数因子如此之大,以至于它基本上总是比简单的n ^ 3实现更合理的矩阵大小.这完全取决于.

Answer 2

那么,"算术运算"并不是唯一可以计算的东西.这并不像其他一切都是免费的.

我天真的猜测是,所有这些内存分配和复制都会减少算术运算所带来的收益......

特别是内存访问,当它离开缓存时可能非常昂贵.相比之下,arihmetic操作可以被认为是免费的:-)