c++ - 在大矩阵中复制图 block 的高效算法

Question

我有 N 个大小相同的 MxM 方阵，它们必须复制到一个包含 NxN 矩阵的矩阵中，并以对称方式排列。上半部分和下半部分包含与此方案相同的矩阵的转置版本。

N = 4

m1 m2 m3 m4
m2'm1 m2 m3
m3'm2'm1 m2
m4'm3'm2'm1

生成数据的算法最初只填充上面的行和第一列，其余为空。

m1 m2 m3 m4
m2'0  0  0 
m3'0  0  0 
m4'0  0  0 

我想找到一个有效的索引方案来填充所有大矩阵，从已经填充的行的元素开始。请记住，m1...mn 是大小为 MxM 的方阵，矩阵按列优先顺序排列。矩阵不是很大，因此无需利用太多局部性和缓存相关的东西。

简单的算法如下所示，其中 X 是矩阵。

  int toX = 0, fromX = 0, toY = 0, fromY = 0; 
  for (int i = 1; i < N; ++i) {
    for (int j = 1; j < N; ++j) {
      for (int ii = 0; ii < M; ++ii) {
        for (int jj = 0; jj < M; ++jj) {
          fromX = (i - 1) * dim + ii;
          fromY = (j - 1) * dim + jj;
          toX = i * dim + ii;
          toY = j * dim + jj;
          X(toX, toY) = X(fromX, fromY);
        } 
      }
    }
  }

你能找到更好的方法吗？

Answer 1

根据您的应用程序，可能不需要存储所有这些转置矩阵。如果 m1 是对称的，您甚至可以剔除 m1 矩阵的下半部分。

事实上，甚至可以不理会所有这些矩阵，而是逐 block 进行矩阵运算(标量的加法和乘法很简单， vector 的乘法会稍微复杂一些)

如果你真的需要整个矩阵，你可能会通过对角线填充矩阵来获得略低的操作数，即通过做这样的事情:

int toX = 0, fromX = 0, toY = 0, fromY = 0;

// m1 (note that this part can be sped up further if m1 is symmetric)

for (int ii = 0; ii<M; ii++){        
    for (int jj = 0; jj<M; jj++){
        fromX = ii;
        fromY = jj;
        toX = fromX;
        toY = fromY;
        for (int k=1; k<N; k++){            
            toX += dim;
            toY += dim;
            X(toX, toY) = X(fromX, fromY);
        }            
    }        
}    


// m2 to m(N-1)

for (int i = 2; i < N; i++){    
    for (int ii = 0; ii<M; ii++){        
        for (int jj = 0; jj<M; jj++){
            fromX = i*dim+ii;
            fromY = jj;
            toX = fromX;
            toY = fromY;
            for (int k=i; k<N; k++){            
                toX += dim;
                toY += dim;
                X(toX, toY) = X(fromX, fromY);
                X(toY, toX) = X(fromX, fromY);
            }            
        }        
    }    
}