"transpose-conjugate" 的最快方法

Question

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

Answer 1

如果您的目标是快速执行此操作，那么您不应该费心编写自己的矩阵乘法算法：使用诸如 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 竞争的东西。

"transpose-conjugate" 的最快方法

Fastest way to "transpose-conjugate"

c++

transpose

matrix

matrix-multiplication