问题标签 [matrix-multiplication]

我在 Java 中编写了两个矩阵类，只是为了比较它们的矩阵乘法的性能。一个类 (Mat1) 存储一个double[][] A成员，其中i矩阵的行是A[i]。另一个类 (Mat2) 存储A以及的转置T在哪里。TA

假设我们有一个方阵 M，我们想要 的乘积M.mult(M)。致电产品P。

当 M 是 Mat1 实例时，使用的算法很简单：

在 M 是 Mat2 的情况下，我使用：

这是相同的算法，因为T[j][k]==A[k][j]. 在 1000x1000 矩阵上，第二个算法在我的机器上大约需要 1.2 秒，而第一个算法至少需要 25 秒。我期待第二个更快，但不是这么快。问题是，为什么速度这么快？

我唯一的猜测是第二个算法更好地利用了 CPU 缓存，因为数据以大于 1 个字的块的形式被拉入缓存，第二个算法通过仅遍历行从中受益，而第一个算法忽略了拉入的数据通过立即转到下面的行来缓存（在内存中大约有 1000 个字，因为数组是按行主要顺序存储的），没有任何数据被缓存。

我问过某人，他认为这是因为更友好的内存访问模式（即第二个版本会导致更少的 TLB 软故障）。我根本没有想到这一点，但我可以看出它是如何减少 TLB 错误的。

那么，它是什么？还是有其他原因导致性能差异？

也许您会对如何解决以下问题有所了解。

约翰决定给儿子约翰尼买一些数学玩具。他最喜欢的玩具之一是不同颜色的积木。约翰决定购买不同颜色的 C 块。对于每种颜色，他都会购买 googol (10^100) 块。所有相同颜色的块具有相同的长度。但是不同颜色的块的长度可能会有所不同。Jhonny 决定使用这些块来制作一个 1 xn 的大块。他想知道有多少种方法可以做到这一点。如果存在颜色不同的位置，则认为两种方式不同。该示例显示了一个大小为 5 的红色块、大小为 3 的蓝色块和大小为 3 的绿色块。它显示了制作长度为 11 的大块的 12 种方法。

每个测试用例以整数 1 ≤ C ≤ 100 开始。下一行包含 c 个整数。第 i 个整数 1 ≤ leni ≤ 750 表示第 i 个颜色的长度。下一行是正整数 N ≤ 10^15。

对于 T <= 25 个测试用例，这个问题应该在 20 秒内解决。应该计算答案MOD 100000007（质数）。

它可以推导出为矩阵求幂问题，使用Coppersmith-Winograd算法和快速求幂可以在 O(N^2.376*log(max(leni))) 内相对有效地解决。但似乎需要更有效的算法，因为 Coppersmith-Winograd 意味着一个很大的常数因子。你还有其他建议吗？它可能是数论或分而治之的问题

我有一个矩阵乘法代码，它通过以下矩阵乘以矩阵 A * 矩阵 B = 矩阵 C

现在我想把它变成多线程矩阵乘法，我的代码如下：

我使用结构

我的方法是

我的主要内容是

但我似乎无法得到与第一个矩阵乘法相同的结果（这是正确的）有人能指出我正确的方向吗？

是否存在获得该结果的模式或方法？请在帖子中显示我的图像 我希望我的结果是垂直数字（黑线）乘以水平数字（红线）的乘积

我有一个 OpenGL 场景，上面有一些数字。你能告诉我我需要做什么来计算“渲染”后的数字顶点位置吗？我知道我可能需要手动乘以一些矩阵，但我不知道它们中的哪一个以及如何。

提前感谢您的帮助！

我对矩阵数学很糟糕，但我有一种情况需要缩放一个。该矩阵是此处定义的自定义类的一个实例，我的缩放对象是一个包含 3 个浮点数 (x,y,z) 的向量。我想要我需要的实际代码而不是通用解释，因为我已经走上了这条路，只是不了解所涉及的数学。幸运的是，一旦我可以缩放矩阵，我想要完成的事情就相当简单了。

这里要澄清的是我正在更新的代码。它使用相对变换遍历链接对象的层次结构，并将 mat& 更新为绝对变换：

}

我正在用这个简单的算法执行矩阵乘法。为了更加灵活，我将对象用于包含动态创建的数组的矩阵。

将此解决方案与我的第一个解决方案与静态数组进行比较，速度要慢 4 倍。我可以做些什么来加快数据访问速度？我不想改变算法。

---

编辑

---

我纠正了我的问题！我在下面添加了完整的源代码并尝试了您的一些建议：

• 交换k和j循环迭代 -> 性能改进
• 声明dim()为->operator()() 性能inline改进
• 通过 const 引用传递参数 ->性能损失！为什么？所以我不使用它。

现在的表现几乎与旧porgram中的表现相同。也许应该有更多的改进。

但我还有另一个问题：函数中出现内存错误mult_strassen(...)。为什么？
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc

---

旧程序
main.c http://pastebin.com/qPgDWGpW

c99 main.c -o matrix -O3

---

新程序
matrix.h http://pastebin.com/TYFYCTY7
matrix.cpp http://pastebin.com/wYADLJ8Y
main.cpp http://pastebin.com/48BSqGJr

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

---

编辑

---

以下是一些结果。标准算法 (std)、j 和 k 循环的交换顺序 (swap) 和块大小为 13 (block) 的阻塞算法之间的比较。

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

---

程序
matrix.h http://pastebin.com/TYFYCTY7
matrix.cpp http://pastebin.com/wYADLJ8Y
main.cpp http://pastebin.com/48BSqGJr

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

在 R 中处理矩阵时，可以分别使用 cbind 和 rbind 将它们并排放置或堆叠在一起。在其他维度堆叠矩阵或数组的等效函数是什么？

例如，下面创建了一对 2x2 矩阵，每个矩阵有 4 个元素：

将它们组合成具有 8 个元素的 2x2x2 数组的代码是什么？