有没有任何方法可以将矩阵乘以O(n)复杂度？

Question

我想将两个矩阵相乘,但三重循环具有O(n ³)复杂度.在动态编程中是否存在将两个矩阵与O(n)复杂度相乘的算法？

好吧我们不能得到最好的O(n ^2.81)

编辑:但有没有任何解决方案甚至可以将结果逼近某些特定的否.列和行的矩阵

我的意思是我们得到O(n ^2.81)中最好的一个复杂的解决方案,但结果很完​​美,但是如果有任何解决方案甚至近似矩阵的乘法,因为我们有因子近似等公式.

如果有任何你知道它会帮助我

问候.

Answer 1

目前已知的最佳矩阵乘法算法是具有O(n ^2.38)复杂度的"Coppersmith-Winograd算法", 但它不用于实际目的.

然而,你总是可以使用 具有O(n ^2.81)复杂度的"Strassen算法",但是没有这种已知的算法用于具有O(n)复杂度的矩阵乘法.

Answer 2

在O(n ^ 2)处存在矩阵乘法的理论下界,因为您必须触摸许多存储器位置来进行乘法.正如其他人所说,有些算法将我们降低到O(n ^ 3)以下,但在实际使用中通常是不切实际的.

如果您需要加快速度,可能需要查看Cache Oblivious Algorithms,例如加速性能的这一算法(http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.5650)通过以缓存内聚方式执行操作,确保数据在需要时位于缓存中.

Answer 3

简答:不

答案很长:如果你有特殊类型的基质(例如对角矩阵),有很多方法.更好的矩阵乘法算法可以将你削减到像O(n ^2.4)(http://en.wikipedia.org/wiki/Coppersmith-Winograd_algorithm)这样的东西.我熟悉的主要方法是使用分而治之算法来分解工作负载(而不是我链接的工作负载).

我希望这有帮助!