有谁知道MATLAB用于矩阵乘法的算法及其时间复杂度是多少？
2009年在Matlab Central上回答了这个问题(具体请参见Tim Davis的第二个答复)。 不知道从那以后有什么变化...
为了完整性-如该线程中所述，Matlab使用BLAS(基本线性代数子程序)中的DGEMM(双通用矩阵乘法)例程。
请注意，没有BLAS的单一实现-针对特定的处理器体系结构进行了调整。因此，如果不找出正在使用哪个版本的BLAS，就不能完全确定计算机上正在使用哪种算法。
BLAS规范指定了每个子例程的输入和输出，并为每个子例程的输出提供了可接受的误差范围。只要遵循规范，实现即可自由使用其喜欢的任何算法。
BLAS的参考实现在DGEMM中使用块矩阵乘法算法，该算法具有时间复杂度O(n ^ 3)来将两个n x n矩阵相乘。我认为可以合理地假设，大多数BLAS实现将或多或少地遵循参考实现。
请注意，它不使用朴素矩阵乘法算法
for i = 1:N
for j = 1:N
for k = 1:N
c(i,j) = c(i,j) + a(i,k) * b(k,j);
end
end
end
这是因为通常，整个矩阵都无法放入本地内存。如果不断将数据移入和移出本地内存，该算法将变慢。块矩阵算法将操作分为几个小块，这样每个块都足够小以适合本地内存，从而减少了移入和移出内存的次数。
存在渐近更快的矩阵乘法算法，例如Strassen算法或Coppersmith-Winograd算法，其速率比O(n ^ 3)稍快。但是，它们通常不了解缓存，而忽略局部性-意味着数据需要不断在内存中转移，因此对于大多数现代体系结构而言，总体算法实际上比优化的块矩阵乘法算法要慢。
Wikipedia注意到Strassen算法可能会在单核CPU上提供大于几千个矩阵大小的加速，但是加速可能会达到10％左右，并且BLAS的开发人员可能认为这种情况不值得案例(也就是说，1996年的这篇论文声称对于大于200的n，速度比DGEMM大约提高了10％-尽管我不知道那是多么过时了)。另一方面，Coppersmith-Winograd算法"仅对大型矩阵提供了优势，以至于现代硬件无法对其进行处理"。
因此，答案是Matlab使用幼稚但高效且具有缓存意识的算法来获得快速的矩阵乘法。
我通过创建一些视频来更新此答案，这些视频演示了与朴素算法相比，块矩阵乘法算法的局部性。
在下面的每个视频中，我们将两个8x8矩阵A和B的乘法可视化以创建乘积C = A xB。黄色高亮显示表示在每个矩阵A，B和C中正在处理哪个元素算法的步骤。您可以看到块矩阵乘法如何一次仅在矩阵的小块上工作，并且多次重复使用每个块，从而使必须将数据移入和移出本地内存的次数最小化。
简单矩阵乘法
块矩阵乘法，块大小= 2
块矩阵乘法，块大小= 4
好答案+1。 我更改了"比O(n ^ 3)少操作"的措辞，因为严格来说，两个例程可以是O(n ^ 3)，但是一个例程可以比另一个例程少。
谢谢@ColinTBowers