什么是最好的矩阵乘法算法？
gue*_*est 12 algorithm math matrix matrix-multiplication
什么是最好的矩阵乘法算法？什么对我来说意味着什么？它意味着最快,为今天的机器做好准备.
如果可以,请提供伪代码链接.
Ant*_*lli 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(Apple):http://developer.apple.com/performance/accelerateframework.html
- 一个非优化但可移植的实现,我称之为'vanilla'(来自GSL)
还有其他商业实现,我没有在这里测试:
- MKL(英特尔):http://software.intel.com/en-us/articles/intel-mkl/
- ACML(AMD):http://developer.amd.com/cpu/Libraries/acml/Pages/default.aspx
可能有更好的,但这些是我的头脑(比标准立方复杂度算法更好).
Strassen's - O(N ^ 2.8)
铜匠Winograd - O(N ^ 2.376)
- 它们具有比"标准"O(N ^ 3)算法更好的渐近复杂度,但对于中等大小的矩阵,常数(至少对于Coppersmith-Winograd而言)是非常大的.请参阅mathoverflow上的这篇文章:http://mathoverflow.net/questions/1743/what-is-the-constant-of-the-coppersmith-winograd-matrix-multiplication-algorithm (2认同)
为什么伪代码？为什么要自己实施呢？如果您关注速度,那么可以使用高度优化的算法,包括针对特定指令集的优化(例如SIMD),实现这些算法并不能带来任何真正的好处(除了可能的学习),
看看不同的BLAS实现,例如:
http://math-atlas.sourceforge.net/