问题标签 [strassen]

我试图理解Strassen 的乘法 kxk 矩阵算法的分析。但我仍然不太确定涉及多少操作。有人可以帮助澄清这一点吗？

有人可以以直观的方式解释施特拉森的矩阵乘法算法吗？我已经通过（好吧，试图通过）书和维基中的解释，但它没有点击楼上。网络上使用大量英语而不是正式符号等的任何链接也会有所帮助。有没有什么类比可以帮助我从头开始构建这个算法而不必记住它？

我只是在自学算法和数据结构，我想知道是否有人有 Strassen 矩阵乘法算法的 C#（或 C++）实现？

我只是想运行它，看看它做了什么，并更多地了解它是如何工作的。

我尝试使用 C++ 实现用于矩阵乘法的Strassen 算法，但结果并非如我所愿。如您所见，strassen 总是比标准实现花费更多的时间，并且只有 2 次方的维度与标准实现一样快。什么地方出了错？

g++ main.cpp matrix.cpp -o matrix -O3.

就效率而言，施特拉森算法应该停止递归并应用乘法的最佳交叉点是什么？

我知道这与具体的实现和硬件密切相关，但是对于一般情况，应该有某种指导方针或某人的一些实验结果。

在网上搜索了一下，问一些他们倾向于认为的人

或者

任何人都可以验证/拒绝这些结果吗？

我从某个地方复制了 strassen 的算法，然后执行了它。这是输出

其中strassen1是一种动态方法，strassen2用于缓存，classical是旧的矩阵乘法。这意味着我们古老而简单的经典是最好的。这是真的还是我在某个地方错了？这是Java中的代码。

作为一个实验，我实现了 Strassen 矩阵乘法算法，看看是否真的可以为大 n 带来更快的代码。

https://github.com/wcochran/strassen_multiplier/blob/master/mm.c

令我惊讶的是，大 n的速度要快得多。例如，n=1024 的情况使用传统方法耗时 17.20 秒，而使用 Strassen 方法（2x2.66 GHz Xeon）仅需 1.13 秒。什么——15 倍加速！？它应该只是稍微快一点。事实上，即使是小的 32x32 矩阵，它似乎也一样好！？

我可以解释这么多加速的唯一方法是我的算法对缓存更友好——即，它专注于小块矩阵，因此数据更加本地化。也许我应该尽可能地做我所有的矩阵算术。

关于为什么这么快的任何其他理论？

我一直在寻找 C 中Strassen 算法的实现，最后我找到了这段代码。

要使用该multiply功能：

它将两个矩阵相乘a，b并将结果放入c（d是一个中间矩阵）。矩阵a，b应具有以下类型：

我已经动态分配了四个矩阵a, b, c, d（二维双精度数组）并将它们的地址分配给字段_matrix.d：

此代码成功编译但因n>崩溃BREAK。

施特拉森.c：

斯特拉森.h：

我的问题是如何使用函数multiply（如何实现矩阵）。

斯特拉森

斯特拉森

我很难概念化如何实现这个算法的 Strassen 版本。

对于背景，我有以下迭代版本的伪代码：

对于最初的分而治之版本，我还有以下伪代码：

所以我的问题是，我对分治法的理解是否正确，如果是这样，我该如何修改以允许 Strassen 的方法？（这不是家庭作业。）

（特别是在我很难将其概念化的地方是在递归之前（或之后）实体本身的数学。即 P1 = A(FH)。如果递归正在积极地乘以基本元素，那么 strassen递归处理矩阵上的算术（加减法）？我有以下伪代码来显示我的大脑在哪里：

我正在尝试解决 strassen 算法的奇数矩阵问题。我的实现在某个点截断递归，称之为 Q，然后切换到标准实现。因此，在进行静态填充时，我实际上不需要填充到 2 的下一个幂。我只需要填充到比输入矩阵维度大的最小 m*2^k，使得 m < Q。

我在实现这一点时遇到了一些麻烦——主要是因为我不确定什么是最有效的。我需要遍历所有可能的 m 值，还是从每个给定的输入中递增，测试它们是否满足标准？