"transpose-conjugate" 的最快方法

Fastest way to "transpose-conjugate"

给定矩阵 A 和 P,我需要计算 "transpose-conjugate"(不确定项是什么)

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) 具有更好渐近时间复杂度的矩阵乘法算法,但也确实有许多人过于相信渐近时间复杂度。

此外,根据使用大型矩阵的经验 它们非常稀疏,因此我认为大型密集矩阵乘法的实际案例少于稀疏矩阵乘法。稀疏矩阵乘法的算法与密集矩阵乘法有很大不同。

要回答有关三个矩阵相乘的问题,您应该进行两次矩阵乘法,但顺序可能很重要。查看 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 竞争的东西。