20

我用 C++、Python 和 Java 编写了用于矩阵乘法的程序，并测试了它们乘以两个 2000 x 2000 矩阵的速度（见帖子）。标准的 ikj 实施 - 在在此处输入图像描述- 采用：

  • C++：15 秒（来源）
  • Python：6 分 13 秒（来源）

现在，我已经在 Python 和 C++ 中实现了用于矩阵乘法的 Strassen 算法，在此处输入图像描述就像在维基百科上一样。这些是我的时间：

  • C++：45 分钟（来源）
  • Python：10 小时后被杀死（来源）

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

想法：

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

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

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

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

4 回答 4

17

基本问题是您使用 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 实现更差。这一切都取决于。

于 2012-07-15T21:30:17.767 回答
6

好吧，“算术运算”并不是唯一重要的事情。这不像其他一切都是免费的。

我天真的猜测是，所有这些内存分配和复制都超过了减少算术运算所带来的收益……

尤其是内存访问，当它离开缓存时可能会非常昂贵，相比之下，算术运算可以被认为是免费的:-)

于 2012-07-15T21:37:21.913 回答
0

尽管 Strassen 算法具有较小的大 O 表示法，但为了利用这一点，您需要乘以在大多数标准机器甚至超级计算机上太大而无法求解的矩阵。

这样想

一个问题是 x^3 ，另一个是 X^1.6734 + 8x^(1/2) +x .....

于 2012-07-15T21:34:08.513 回答
0

我记得我在大学时也做过同样的事情。我的实现是用 Java 实现的。我还写了一个脚本来测试代码，我有10000多个不同大小的随机矩阵的测试用例（2 2）~（8192 8192）。我没有让递归进入标量级别，我使用 2 的所有幂作为停止点。我发现了一个 Strassen 算法更有效的范围，以及一个比朴素算法更差的范围。

我没有调查缓存、内存或 JVM（垃圾收集）。

当我在课堂上展示时，我将这些发现归因于 Strassen 算法的渐近复数是根据乘法次数来衡量的。它是在计算机做加法比乘法更快的时候设计的。

如今，CPU 的速度与它们添加的速度一样快（周期数）。如果检查这两种算法，您会发现只有当大小小于 2^10 时，Strassen 的算术运算才比朴素算法少（如果我没记错的话）

于 2021-05-27T14:43:06.903 回答