问题标签 [strassen]

结果是 Strassen() : 27 秒和 muliply_mat() : 5 秒

我怎样才能比 multiply_mat() 更短？

我猜问题是 strassen 函数中的 new_mat 函数。

我应该怎么做才能减少使用 strassen 函数的时间。

我想这段代码很长。

我怎样才能从 strassen() 中摆脱这种情况？

我的任务是用 C++ 编写 Strassen-Winograd 算法。我已经写了两次，但我的代码的第一个版本不起作用。结果矩阵左下角的结果是正确的。即使 N = 64+，我的第二个版本的运行速度也比简单算法慢。

我究竟做错了什么？

重要提示：我不允许在递归和结构中使用动态矩阵。此外，最好不要复制，使用子矩阵角元素的坐标进行乘法运算。

不正确：

慢，最后期限默认1：

我正在学习算法课程，刚刚了解了 Strassen 的矩阵相乘算法。我已经在节点中实现了这个，它适用于小矩阵。我想在一个非常大的矩阵上进行测试，但是当我尝试创建它时节点核心转储。我能够创建大小为 10000 的第一个矩阵，但是当我尝试创建第二个矩阵时它崩溃了。下面的完整堆栈跟踪：

我包括用于创建矩阵的代码：

这个问题有什么解决办法吗？

我正在尝试测试矩阵乘法的朴素和施特拉森方法。

然而，Strassen 算法的工作速度比天真的方法慢得多。对于 1024 大小的矩阵，朴素方法在 3542 毫秒内完成，而 Strassen 在 83602 毫秒内完成。（Strassen 不使用截断/幼稚的方法）这是我正在使用的 Strassen 代码。LEAF SIZE 是它切换到幼稚方法的数字：

叶子大小在 32 左右，它确实执行得更快（这是天真的算法开始的截止点）

这是Java语言。代码来自互联网，但或多或​​少所有的实现都是相似的。

没有切入点，仅凭 Strassen 就无法击败幼稚吗？任何想法，将不胜感激。谢谢你。

编辑添加了加法和减法。

EDIT2从代码中创建新子矩阵的最大开销是什么？如果是这样，可以应用什么方法来消除尽可能多的开销？如果在 java 中什么都做不了，我不反对使用 c++。

EDIT3任何人都可以提出一种方法来减少这里使用的内存分配吗？将不胜感激的建议。

我正在学习算法课程。在谈到分而治之时，我遇到了施特拉森算法。

所以，问题是我们如何乘以奇数度的矩阵，或者不是 2 的幂的偶数度数？

此外，我们如何将 Strassen 算法应用于不同维度的矩阵（例如将 2X3 矩阵与 3X1 矩阵相乘）？

所以我在 C 中实现了 Strassen 算法，即使对于大型矩阵，它也无法击败经典的 ikj 算法。我只使用 2 的幂的矩阵，填充双精度数。我读到对于“大”n，Strassen 算法击败了经典算法，例如对于 n >= 1000。对我来说，情况并非如此。我不使用截止点，因为它不是原始算法的一部分。如果我这样做了，它实际上比经典的要快，但如果没有它，它的表现会更糟。这是预期的行为吗？我在网上找到的关于 Strassen 算法的资料实际上是在使用截止点吗？

我尝试优化 Strassen，只使用存储为一维数组的两个矩阵，将它们作为参数传递，如果可能的话实际上不创建子矩阵，但只是将新大小和指针传递给两个单元格，所以我不分配为很多内存。但也许对于大型矩阵来说，这实际上很糟糕，因为我正在访问整个矩阵并且需要将它存储在主内存中的某个位置。

这是一个 Github 链接：https ://github.com/AlexLoitzl/matmul 该代码尚未正确记录...这里是 Strassen 实现：

我尝试使用 Strassen 算法编写矩阵乘法代码。该代码有效，但是当我尝试使用随机生成的方阵将结果与简单算法（n^3）进行比较时。编译时没有警告，但程序使用的内存以某种方式不断增加。我对 C++ 相当陌生，指针对我来说是一个全新的概念。即使经过故障排除，我也找不到内存泄漏。很抱歉发布整个代码。

我已经尝试删除那些在没有被使用的情况下被覆盖的冗余定义。

我一直在用线程实现 Strassen 算法。我已经通过结构将数据传递给线程并通过函数启动它们pthread_create()。问题是我正在操作 std::vector < std::vector<int> > ，我不能通过引用将它传递给结构。我做了一些研究并决定使用std::ref 它来包装内容并将其发送到功能。退出功能后问题开始；r1 值没有变化（内部变化），所以有些地方不正确。

示例代码：

如何解决？

注意： *add_Thread() 工作正常；我在我的程序中使用数组。这里的代码只是为了展示想法。

我试图弄清楚如何在javascript中实现这个算法，但我在这部分真的很困惑：

将输入矩阵 A 和 B 以及输出矩阵 C 划分为 n/2 * n/2 个子矩阵。

任何人都可以帮忙吗？

在 MITOpencourseware（6.006 第 12 课）中进行 MIT 讲座时，我遇到了 4 种乘法算法（将两个 n 位数字相乘）-

1. O(n^2) 复杂度的普通朴素方法
2. Karatsuba 算法 - O(n^1.584)
3. Toom-Cook(Toom3) - O(n^1.465)
4. Schonhage-Strassen - O(nlog(n)log(log(n)))

现在要研究的是，在哪个阈值点（即 n 的值），一种方法作为更好的算法超越了另一种方法。有人提到以上所有内容都在 gmpy 包中。

为了尝试这一点，我参考了以下链接中的 gmpy2 包文档 - https://gmpy2.readthedocs.io/en/latest/intro.html

然而，在浏览本文档的部分内容时，gmpy2 似乎更多的是处理大量数字。特别是，我没有找到实现上述 4 种算法的单独函数。那么 gmpy2 的任何部分是否实现了这些算法，所以我可以根据 n（位数）绘制这些算法的运行时间？