问题标签 [strassen]

我们有一个矩阵，其元素在整数模 2 (F_2) 的字段中。我们正在寻找将 nxn 矩阵乘以 F_2 的算法O(n^2.81/(log n)^0.4)

怎么可能？

我知道，Strassen 的算法给出了O(n^2.81)，但是我们怎么能得到这个因子(log n)^0.4呢？

我正在使用 python 实现 Strassen 的矩阵乘法。在划分步骤中，我们将较大的矩阵划分为较小的子矩阵。是否有内置的 numpy 函数来拆分矩阵？

我用 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 矩阵乘法器这么快？
• 矩阵乘法：Strassen vs. Standard - Strassen 对他来说也较慢，但至少处于同一数量级。

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

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

我想知道您将如何在 Strassen 的算法中进行递归调用，以及它们究竟需要在哪里。

我知道 7 个乘数比我们原本拥有的 8 个更有效，但我对如何递归计算这些乘数感到困惑。特别是，如果我们遵循分而治之的范式，我们究竟要“划分”矩阵的哪一部分，以及在我们达到可以分别征服递归部分的基本情况之前，我们将如何做呢？

谢谢！

我正在尝试在 Java 中实现 Strassen 算法，我正处于需要将输出组合成单个矩阵/二维数组的步骤。我System.arraycopy用来复制数组，这适用于以自上而下的方式连接两个数组，但是，我还需要并排连接它们，我遇到了麻烦。我遇到了ArrayOutOfBoundsException。这是我的代码

最后一行

抛出异常。有没有办法并排连接数组（以列方式）？

假设我有一个 NxN 矩阵，其中包含 1 到 10 范围内的随机整数。现在，我想调用 PROC(A(1:n/2, 1:n/2)+A(n/2+1:n, n/2+1:n)...其中 n 是矩阵的大小。换句话说，我想从 A 的第一行和第一列开始创建一个子矩阵，直到 A 的一半大小，然后将其添加到一个子矩阵，该子矩阵从 A 的一半大小加一开始，直到结束一种。

我使用的分区函数是这样的：

现在，这适用于查找给定矩阵左上角 ( Matrix C = m.partition(1, m.size()/2, 1, m.size()/2);) 的子矩阵。

但是，当我尝试获取另一个子矩阵 ( Matrix D = m.partition(m.size()/2+1, m.size(), m.size()/2+1, m.size());) 时，我得到一个ArrayIndexOutOfBoundsException: 2. 我尝试向我的分区函数添加单独的行和列计数器，但它给出了相同的错误。如何修改我的分区函数以处理所有输入并仍然提供正确的输出？

我正在尝试在 Python 中实现 Strassen 矩阵乘法。我已经让它工作了一些。这是我的代码：

我包括了直接矩阵乘法以参考正确的所需输出。基本上会发生这种情况：

施特拉森输出：

应该：

我不确定问题的根源是什么，这意味着我无法解决它！

我用 C++ 编写了两个矩阵乘法程序：Regular MM (source)和 Strassen's MM (source)，它们都在大小为 2^kx 2^k 的方阵上运行（换句话说，是偶数大小的方阵）。

结果很糟糕。对于 1024 x 1024 矩阵，Regular MM 需要46.381 sec，而 Strassen 的 MM 需要1484.303 sec( 25 minutes!!!!)。

我试图使代码尽可能简单。在网上找到的其他 Strassen 的 MM 示例与我的代码没有太大区别。Strassen 的代码的一个问题是显而易见的——我没有切换到常规 MM 的截止点。

我的 Strassen 的 MM 代码还有什么其他问题？？？

谢谢 ！

直接链接到来源
http://pastebin.com/HqHtFpq9
http://pastebin.com/USRQ5tuy

编辑1。拳头，很多很好的建议。感谢您抽出宝贵时间分享知识。

我实施了更改（保留了我的所有代码），添加了截止点。MM 的 2048x2048 矩阵，截止 512 已经给出了很好的结果。常规 MM：191.49s Strassen 的 MM：112.179s 显着改善。结果是在配备 Intel Centrino 处理器的史前联想 X61 平板电脑上使用 Visual Studio 2012 获得的。我会做更多检查（以确保我得到正确的结果），并将公布结果。

嗯，是《算法导论》中的一道题，编号为4.2-6。它是这样描述的：

a kn*n matrix by an n*kn matrix使用Strassen's algorithmas时，您能以多快的速度繁殖subroutine？

我正在考虑将两个矩阵都扩展到kn*kn matrix，然后我可以将 Strassen 的算法应用于这个问题。但我会得到一个Math.pow(kn, lg7) running time.

有没有人有更好的解决方案。祝大家新年快乐。

我正在努力确定为什么我的 Strassen 实施如此缓慢。它为每次迭代分配内存，但我会酌情释放它。