Эффективный алгоритм копирования плиток в большую матрицу

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.

На самом деле, возможно, было бы даже целесообразно оставить все эти матрицы в покое и выполнять свои матричные операции блочно (сложение и умножение со скаляром просты, умножение с вектором было бы немного сложнее)

Если вам действительно нужна вся матрица, вы можете получить немного меньший счетчик операций, заполнив матрицу по диагонали, то есть сделав что-то вроде этого:

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);
            }            
        }        
    }    
}