问题标签 [strassen]

有人可以帮我分解一下吗？为什么不能在两次乘法中完成？

复数的乘法

如果将计算所需的乘法次数视为其难度的衡量标准，并且这些计算是使用复数执行的，那么很自然地会问需要多少实数乘法来评估复数乘积的实部和虚部。形成复数乘积的自然方式需要四次实数乘法。然而，它可以用三个而不是两个乘法来完成。

定理- 计算两个复数的乘积需要三个实数乘法，即使乘以实数常数不计算在内。

证明草图由于复数乘法的实部和复数部分都不能在一次实数乘法中确定，如果这个计算可以在两次乘法中完成，那么对于 C _i、 W _i、 X _i的某些选择，它将完成， Y _i和 Z _i以下列方式。

这导致 20 个未知数中的 20 个非线性方程，C _i，W _i，X _i，Y _i和 Z _i其中 (i = 1,2,3,4)，它们没有实解，因此没有在两个实数乘法中执行复数乘法的方法

资源：

门罗，伊恩。“40-44。” http://dl.acm.org/。过程。第三届 ACM 计算理论年度研讨会论文集，俄亥俄州，Shaker Heights。埃德。Michael A. Harrison、Ranan B. Banerji 和 Jeffrey D. Ullman。ACM，1971 年 5 月 3 日。网络。2016 年 11 月 26 日。http://dl.acm.org/citation.cfm?doid= 800157.805036。

我正在尝试在 C++ 中实现 Strassen 的矩阵乘法算法，并且我想找到一种方法在恒定时间内将两个矩阵分成四个部分。这是我目前这样做的方式：

这种方法显然是 O(n^2)，它会将 n^2*log(n) 添加到运行时，因为每次递归调用都会调用它。

似乎在恒定时间内执行此操作的方法是创建指向四个子矩阵的指针，而不是复制值，但我很难弄清楚如何创建这些指针。任何帮助，将不胜感激。

在过去的几个小时里，我一直在尝试实现 Strassen 的矩阵乘法算法，并且在获得正确的产品时遇到了麻烦。我认为我的辅助函数之一（helpSub、createProd、helpProduct）可能是我的 strass2 函数的问题或格式（命令顺序等）。任何提示都会受到欢迎，因为我完全被难住了。我一直在使用两个 4 x 4 矩阵作为测试矩阵。我已经尝试了很多我在互联网上看到的 p1-p7 和 c1-c4 变体，但似乎都没有。下面是我创建的课程。

如果有任何令人困惑的地方，请告诉我，我会更新问题！

这是主要功能::

以下是目前的结果（预期结果是显示的第一个 4x4 矩阵，实际结果是显示的最后一个 4x4 矩阵）：

我很确定我的 helpSub() 函数可以正常工作，因为它们产生了更正的啊。但是，我在 strass2 递归调用中使用的参数可能存在问题。很抱歉，如果它不够具体，我只是对此有点筋疲力尽，并且很好奇是否有人看到任何明显的问题。

我正在为 Strassen 的矩阵乘法编写程序，但出现以下错误：

以下是所有相关代码：

用 Strassen 存在的方程：

假设一个 nXn 矩阵，其中 n 是 2 的精确幂

为什么会发生 TypeError？我意识到所有功能链接都必须存在一些问题，但是如果有人指出我正确的方向，那就太好了。

我在 R 中的 cxx 函数有问题。我想自己调用它，不幸的是，编译器给了我这个错误消息：

'Matmult2' 未在此范围内声明

问题还在于调用Matmult2cxx 函数。

我最初的问题与 strassen 算法有关，我想用 RCPP / Inline 递归调用。非常感谢您的帮助！

`

')

`

我正在尝试使用 Python 3 和 numpy 矩阵实现 CLRS 中描述的 Strassen 矩阵乘法算法。

问题是输出矩阵 C 作为零矩阵返回，而不是正确的乘积。我不确定为什么我的实现不起作用，但怀疑这与每次递归调用创建 C 矩阵有关。对于我做错了什么以及如何解决它，我将不胜感激。

谢谢！

我已经为 strassen 算法http://www.sanfoundry.com/java-program-strassen-algorithm/实现了以下代码 。它适用于大多数矩阵，包括 2x2 和 4x4 矩阵，但不适用于 3x3 矩阵。任何想法为什么以及如何解决它？

所以，我想弄清楚 strassen 的矩阵乘法方法，我使用的是 C++，但它可以是任何语言。现在，它看起来像：

我不确定接下来如何处理各个象限，即此时如何导出 M1-M7 矩阵。我想 M1-M7 矩阵（与基本情况下的原始数据类型相反）将以与基本情况相同的方式使用。我只是不确定这里的解散会是什么样子。

我知道阅读别人的代码有点困难，但希望它已经清楚了。

我确信我的基本情况是正确的，并且我确信我正确地拆分了矩阵，我只是不清楚下一步该去哪里。也许我写错了我的算法。

我需要使用常数空间将两个矩阵相乘。请注意，运算后的结果应存储在其中一个矩阵中。打印结果而不存储是微不足道的。通常，任何标准算法都会定义一个相同大小的新矩阵，用于存储所有临时结果和最终结果。它甚至可以优化为使用单个数组。但是想不出任何机制可以在恒定空间中做到这一点。直观地说，这可以被认为等同于找出在不使用临时变量的情况下将两个 2x2 矩阵相乘的算法？

通过 Strassen 的算法和 Python 3 中的朴素嵌套 for 循环实现，我得到了不同的矩阵乘法输出。

代码：

输出：

$ python3 斯特拉森.py

a = [[11, 11, 11, 11], [22, 22, 22, 22], [33, 33, 33, 33], [44, 44, 44, 44]]

b = [[101, 181, 119, 113], [22, 22, 22, 22], [33, 33, 33, 33], [44, 44, 44, 44]]

使用 Strassen 算法：

a*b = [[2200, 3080, 2398, 2332], [4400, 6160, 4796, 4664], [6600, 9240, 7194, 6996], [8800, 12320, 9592, 9328]]

使用朴素算法：

a*b = [[2200, 2200, 2200, 2200], [6160, 6160, 6160, 6160], [7194, 7194, 7194, 7194], [9328, 9328, 9328, 9328]]

任何人都可以帮忙吗？