矩阵乘法中最快的方法是什么？

Question

我最近一直在开发一个相当复杂的程序，目前我需要使用矩阵乘法。问题是，对于这个特定的程序，速度至关重要。我熟悉许多矩阵设置，但我想知道哪种方法运行得最快。我已经进行了广泛的研究，但结果很少。以下是我熟悉的矩阵乘法算法列表：

- 迭代算法 - 分治算法 - 亚立方算法 - 共享内存并行性

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

- Evan Sanderson

---

手动调整的库是由具有处理器架构详细知识和经验的专家开发的，也就是说不要自己编写代码，可以借鉴或者抄袭一个实现。或者直接购买一个。 - High Performance Mark

这个问题太宽泛了。你的矩阵可以是大的、小的、稀疏的、密集的... 没有适用于所有情况的最佳算法。请注意，共享内存并行性不是一个算法，而且根据你所处的并行架构，有些算法表现更好，有些则表现更差。 - coincoin

请查看相关帖子。 - Axel Kemper

Answer 1

斯特拉森算法和朴素的（O(n^3)）算法是实践中最常用的。

更复杂的算法有着更紧密的渐近界限，但由于其复杂性，它们的优势只有在矩阵非常大时才会显现，例如Coppersmith 算法。

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

- igon

---

我是一个葡萄柚！ - coincoin

这个回答中第一条陈述有什么证据可以由OP（或任何其他人）提供吗？ - High Performance Mark

有很多论文研究这个主题。从这篇文章来看，Strassen在处理大矩阵时能够显著提高速度，而Coppersmith的好处非常有限。但是，在具有复杂内存层次结构的系统上，Strassen本身可能不方便；这篇文章建议在ATLAS中添加一个额外的自动调整步骤，以自动决定是使用Strassen还是朴素方法进行DGEMM。 - igon

有很多论文研究这个主题。当然，目前广泛使用的矩阵计算库实际上并没有采用 Strassen 算法的证据很少。正如您所写的那样，“在具有复杂内存层次结构的系统上，Strassen 本身可能不方便”，这几乎涵盖了当前基于 CPU 的计算机的大部分情况。 - High Performance Mark

当然，尽管关键点是即使对于一个固定的平台，最佳方法也取决于乘法的大小。无论如何，我改变了我的答案以反映出这个问题仍然有争议。 - igon

Answer 2

最快的方法可能是使用已经优化过的现有库，您不必每次都重新发明轮子。

- Mathieu Borderé