c++ - “transpose-conjugate”的最快方法

给定矩阵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];
            }
      }
}

但是，这是O(n ^ 4)，我也可以将其作为两个常规矩阵乘法来进行，所以是两次O(n ^ 3)。我在这里错过什么还是应该坚持两次乘法

X = A Transpose(P)
X = P X

最佳答案

如果您的目标是快速做到这一点，那么您就不必费心编写自己的矩阵乘法算法:使用诸如Eigen之类的库。确实存在比O(n ^ 3)更好的渐近时间复杂度的矩阵乘法算法，但是也确实有很多人对渐近时间复杂度抱有太多的信心。

另外，从使用大型矩阵in scientific research的经验来看，它们非常稀疏，因此我认为大型密集矩阵乘法的实际案例少于稀疏矩阵乘法的实际案例。稀疏矩阵乘法的算法与密集矩阵乘法的算法非常不同。

要回答有关将三个矩阵相乘的问题，您应该将矩阵相乘两次，但是顺序很重要。查看Matrix_chain_multiplication。矩阵乘法是关联的。让我们使用Wikipedia中的示例。 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，线程化以及汇编。几周后，您可能会写一些与本征竞争的产品。

关于c++ - “transpose-conjugate”的最快方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34330189/