问题标签 [strassen]

这是我第一次提出问题，如果我做错了什么，请原谅我。

我正在尝试在 matlab 中编写 Strassen 的算法，它似乎可以工作，但速度很慢（取决于截止时间，对于 64x64 矩阵，它已经可能需要一秒钟以上的时间）。

它比简单的实现（有 3 个循环）要慢。我做错了什么吗？下面是函数，输入的大小已经正确（2^n）

使用与Strassen相同的方法，仅 5 次乘法就足以计算矩阵的平方。如果 A[2][2] = [a, b, c, d]，则乘法为 a * a, d * d, b * (a + d), c * (a + d), b * c。

如果我们推广该算法以获取矩阵的平方，则复杂度降低到以 2 为底的 n^log5。

我被问到这个算法有什么问题，如果我们推广这个算法来找到矩阵的平方，它什么时候会失败？

作为作业的一部分，我试图找出 Strassen 矩阵乘法和朴素乘法算法的交叉点。但同样，当矩阵变为 256x256 时，我无法继续。有人可以建议我适当的内存管理技术来处理更大的输入。

代码在C中如下：

稍后添加如果我尝试使用 malloc 语句进行内存分配，代码如下。但问题是它在朴素矩阵乘法方法之后停止，甚至没有进行 N=1 的 Strassen 方法。它显示关闭程序的提示。

这是我关于stackoverflow的第一个问题。我一直在解决一些来自塔马西亚古德里奇的“算法设计”的练习。但是，我对这个问题一无所知。Unusere 从哪里开始以及如何进行。任何建议都会很棒。这是问题所在：

布尔矩阵是每个条目为 0 或 1 的矩阵，矩阵乘法通过使用 AND 表示 * 和 OR 表示 + 来执行。假设我们有两个 NxN 随机布尔矩阵 A 和 B，因此其中任何一个条目为 1 的概率为 1/k。证明如果 k 是一个常数，那么有一个算法将 A 和 B 相乘，其预期运行时间为 O(n^2)。如果 k 是 n 怎么办？

有一个用于整数乘法的 Strassen 算法版本，它使用三向拆分（将 n 位数分成 n/3 位的 3 部分）并采用 O(n^1.46)。

我的问题是为什么这种方法通常不优于使用 O(n^1.59) 的 2 路拆分的常用方法？任何可以帮助我理解的想法或链接？（我在网上查过，但没找到）

我使用指针编写了基于 Strassen 乘法算法的并行程序。该程序返回两个大小相同的矩阵相乘的结果。当大小为 256 时，程序会填充大约 1 GB 的内存，当它总共是 512 内存时\y 已满并且我的 Windows 无法工作，那么我必须重新启动。

我用向量替换了整个指针，然后令人难以置信的 Ram 使用量减少了！.对于 1024 大小，只使用了 80 MB 的 ram。

我对最初静态绑定的向量有所了解，然后如果我们在运行时需要更多空间，它会动态绑定。

为什么指针比向量需要更多空间？

这是我的第一个代码：

我用向量替换整个指针数组：

我想知道 Strassen 的算法是否可以用于布尔矩阵乘法？我知道它用于常规矩阵乘法，但对布尔值不太确定。

另外，如果可以的话，它是否比使用四俄罗斯人方法更快，并且通常应该用于布尔乘法？

我是一个新手，我试图实现 Strassen 的算法来将两个 NxN 矩阵相乘。我目前正在研究均匀尺寸。对于大于 4 的 N 值，我遇到了分段错误。

调试后，我发现在第一次调用乘法函数之前和显示两个矩阵之后立即遇到分段错误。

任何帮助表示赞赏。

非常感谢！

设计和分析一种算法，将 2 个数字 A 和 B 相乘，每个 n 位长，但使用 Strassen 算法将它们分成 3 个相等大小的块。您可以获得的最佳运行时间是多少？

我有两个长度为 n 的数字并将它们分成三个相等的部分。例如，123 分为 1、2 和 3。根据我的理解，我必须使用矩阵。但是，Strassen 的算法对我来说没有任何意义。

我看过视频和阅读讲座，但仍然不知道如何进行。任何帮助将不胜感激，谢谢！

Caesar 教授希望开发一种矩阵乘法算法，该算法在渐近上比 Strassen 算法更快。他的算法将使用分而治之的方法，将每个矩阵分成大小为 n/4 xn/4 的块，并且分而治之的步骤将花费 Theta(n^2) 时间。