最快的转位方法-共轭

提问者：小点点

最快的转位方法-共轭

给定矩阵A和P，我需要计算“转矩-共轭”（不确定是什么）

X = P A Transpose(P)

我在想最快的方法是

for(int i=0;i<n;i++) {
      for(int j=0;j<n;j++) {
            for(int k=0;k<n;k++)
                    for(int l=0;l<n;l++) X[i][j]+=P[i][l]*A[l][k]*P[j][k];
            }
      }
}

但是这是On4)，我也可以做两次常规矩阵乘法，所以两次On3)。我是遗漏了什么，还是应该继续做两个乘法

X = A Transpose(P)
X = P X

共1个答案

匿名用户

如果您的目标是快速完成此操作，那么您不应该麻烦编写您自己的矩阵乘法算法:使用一个库，例如Eigen。确实有一些矩阵乘法算法的渐近时间复杂度比O(N3)更好，但也确实有很多人过于相信渐近时间复杂度。

而且，从科学研究中处理大型矩阵的经验来看，它们是相当稀疏的，所以我认为大型稠密矩阵乘法的实际情况比稀疏矩阵乘法要少。稀疏矩阵乘法的算法与稠密矩阵乘法的算法有很大的不同。

要回答关于三个矩阵相乘的问题，您应该做两次矩阵相乘，但顺序可能很重要。研究matrix_chain_multiplication。矩阵乘法是相联的。让我们使用维基百科中的例子。A是一个10×30的矩阵，B是一个30×5的矩阵，C是一个5×60的矩阵。然后，

(AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations
A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations.

当所有的矩阵都具有相同的大小时（就像你的问题中所提到的那样），这就无关紧要了。

如果您计划继续优化CPU上的密集矩阵乘法，您将需要使用循环平铺，SIMD，线程，也许还有汇编。几个星期之后，你可能就可以写出和Eigen竞争的东西了。