最好的矩阵乘法算法是什么？对我来说“最好的”是什么意思？这意味着最快且为当今的机器做好准备。
如果可以的话，请给出伪代码的链接。
问问题
18490 次
8 回答
12
BLAS 是最好的即用型高效矩阵乘法库。有许多不同的实现。这是我在具有双核 Intel Core 2 Duo 2.66 GHz 的 MacBook Pro 上为某些实现所做的基准测试：
- gotoBLAS2（开源）：https ://www.tacc.utexas.edu/research-development/tacc-software/gotoblas2
- ATLAS（开源）： http: //math-atlas.sourceforge.net/
- Accelerate.framework（苹果）：http: //developer.apple.com/performance/accelerateframework.html
- 一个未优化但可移植的实现，我称之为“香草”（来自 GSL）
还有其他我没有在这里测试的商业实现：
- MKL（英特尔）： http: //software.intel.com/en-us/articles/intel-mkl/
- ACML（AMD）：http: //developer.amd.com/cpu/Libraries/acml/Pages/default.aspx
于 2010-12-16T09:51:00.917 回答
8
最好的矩阵乘法算法是具有详细架构知识的人已经针对您的目标平台手动调整的算法。
有很多很好的库可以提供经过调整的矩阵乘法实现。使用其中之一。
于 2010-12-15T22:50:04.523 回答
8
于 2010-12-15T22:53:48.357 回答
6
为什么是伪代码？为什么要自己实现？如果您关心速度，可以使用高度优化的算法，包括针对特定指令集（例如 SIMD）的优化，自行实现这些并没有真正的好处（除了可能学习），
看看不同的BLAS实现，例如：
于 2010-12-15T22:38:43.843 回答
3
这是麻省理工学院的算法课程和矩阵乘法讲座
矩阵乘法 - O(n^3)
Strassen 算法 - O(n^2.8) http://en.wikipedia.org/wiki/Strassen_algorithm
Coppersmith–Winograd - O(n^2.376) http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm
于 2010-12-16T05:38:59.830 回答
2
取决于矩阵的大小，以及它是否稀疏。
对于中小型密集矩阵，如果您注意缓存一致性并使用平台的向量指令，我相信“朴素” O(N^3) 算法的一些变化是一种胜利。
数据排列很重要——对于标准矩阵布局对缓存不友好的情况（例如，列优先 * 行优先），你应该尝试矩阵乘法的二进制分解——即使你不使用 Strassen 或其他“快速”算法，这种操作顺序可以产生一个“缓存忽略”算法，自动充分利用每一级缓存。如果您有幸重新排列矩阵，您可以尝试将其与数据元素的位交错（或“Z-order”）排序结合起来。
最后，请记住：过早优化是万恶之源。当它不再为时过早时，始终在优化之前、期间和之后进行分析和基准测试......
于 2010-12-16T00:54:53.730 回答
0
有一种算法称为Cannon's algorithm分布式矩阵乘法算法。更多在这里
于 2010-12-15T22:37:44.230 回答
0
所有现代 CPU 上的所有矩阵都没有“最佳算法”。
您将需要对许多可用的方法进行一些研究，然后为您正在处理的特定硬件上计算的特定问题找到最合适的解决方案。
例如，硬件平台上“最快”的方法可能是使用“慢”算法，但要求 GPU 将其并行应用于 256 个矩阵。或者使用“快速”通用 (mxn) 算法可能会产生比使用优化的 3x3 矩阵乘法慢得多的结果。如果您真的希望它更快，那么您可能需要考虑使用裸机，以确保充分利用特定的 CPU 功能，例如 SIMD 指令、分支预测和缓存一致性，但会牺牲可移植性。
于 2010-12-15T23:07:22.400 回答