一个快速算法来计算矩阵乘法

Question

在c++代码的中间，使用eclipse，我需要计算矩阵A和B的乘积，大小为2400*3600（因此维度不同）。矩阵存储在浮点型二维数组中。它们不是稀疏的，没有限制。

每次相乘都需要很长时间（几分钟），我需要严重减少这个时间，因为我有一个循环，重复5000万次。每次都需要将新的A和B相乘。欢迎任何建议以减少时间复杂度（即使更改数据存储结构，如果您认为可能会有所帮助）。例如，如果我将数据存储到一维数组中会怎样？或者使用向量代替数组？

在一个特定的情况下，第一列总是1，值为1、-1或零。对于这种情况有什么想法吗？

在其他情况下，值可以是任何东西。其中之一是X与其转置相乘。对于这个特定的情况是否有任何建议？

- Pegah

---

通用矩阵乘法的朴素算法是O(n^3)，但有方法将其降至约为O(n^(2.7))。如果在开始计算之前无法减少一些工作量，这只是一个非常庞大的计算。如果大量数字源自一组连续的变换，也许您可以每行进行一次转换并找到差值，或者做些其他什么。 - dmckee --- ex-moderator kitten

你的矩阵大部分都是零吗？如果是这样，那么也许你可以找到一个操作稀疏矩阵的乘法算法。稀疏矩阵本质上是一个(i,j)->value映射。 - Emile Cormier

Answer 1

我不会浪费时间来尝试编写自己的数值计算库：可以在谷歌上搜索LAPACK或BLAS，这是两个经过时间考验的数值计算包，都经过了极致的优化。这两个包都有可用的C API。

- Ernest Friedman-Hill

---

+1：这两个库不仅使用了优化算法，还使用了基于SSE指令的优化实现。 - Matthieu M.

Answer 2

将第二个矩阵转置后存储，可以帮助列与缓存行匹配，而不是行。L2缓存和主内存之间的访问时间差异约为10倍。

- Ben Voigt

---

虽然看起来很明显，但我不理解你的意思。能否再解释一下？如果我真的想要把A乘以它的转置呢？ - Pegah

@Pegah：如果您查看矩阵乘法算法，您会发现内部循环看起来像这样：sum = 0; for( int k = 0; k < n; ++k ) sum += a[i][k] * b[k][j]; c[i][j] = sum;。连续的迭代访问了 a[i][0]、a[i][1]、a[i][2]，这是可以的，因为它们在内存中相邻，所以缓存可以一次从主存中读取大块数据。但是您还要访问 b[0][j]、b[1][j]、b[2][j]，这种访问方式的局部性非常差，缓存必须执行许多单独的从主存中传输，这是非常浪费的。 - Ben Voigt

Answer 3

你可以试一试Eigen。

- genpfault

Answer 4

如果你要进行数百万次的乘法计算，我会首先转向像CUDA或DirectCompute之类的东西来将工作卸载到GPU上，因为GPU更适合这种工作。这就是MATLAB所做的，即使GPU加速是可选的。

有很多例子展示了使用GPU加速矩阵乘法的方法，所以你的工作不应该太难。

- Blindy

---

实际上，我需要在C++代码的中间执行它，并且其结果由代码的其余部分使用。因此，这不是一个独立的任务。据我所了解（我刚才在网上搜索），GPU是一种基于硬件的实现，而Directcompute是一个单独的应用程序。我错了吗？还是我仍然可以在我的代码中使用GPU？ - Pegah

我不知道你在说什么。CUDA 和 DirectCompute 是允许你在 GPU 上执行算术运算的 API。基于硬件实现的是什么？嵌入到 C++ 代码中间？与什么相对呢？ - Blindy

@Pegah 是的，你的GPU很可能是基于硬件实现的 :) - Christian Rau

@Pegah：GPU只是指您的显卡上的处理器芯片。它非常擅长同时执行许多相同的操作，但在复杂的分支方面表现不佳。矩阵乘法是很多相同操作的集合，因此在GPU上运行非常快。DirectCompute、CUDA和OpenCL是库，允许C++程序向您的显卡发出指令并移动数据。 - Ben Voigt