algorithm - 最快的矩阵乘法是什么？

Question

我最近一直在研究一个相当广泛的程序，目前我正处于必须利用矩阵乘法的地步。事情是，对于这个特定的程序，速度是至关重要的。我熟悉许多矩阵设置，但我想知道哪种方法运行最快。我做了广泛的研究，但结果很少。这是我熟悉的矩阵乘法算法的列表:

• 迭代算法
• 分而治之算法
• 次三次算法
• 共享内存并行

如果有人需要澄清我列出的方法或一般问题，请随时提问。

Answer 1

Strassen算法和朴素 (O(n^3)) 算法在实践中使用最多。

没有使用具有更严格渐近界限的更复杂的算法，因为它们的好处仅适用于非常大的矩阵，因为它们的复杂性，例如Coppersmith算法。

正如其他人指出的那样，您可能希望使用像 ATLAS 这样的库这将根据您正在执行的平台的特性自动调整算法，例如L1/L2 缓存大小。