Оптимизация памяти Matrix Div and Conquer

В настоящее время я реализую алгоритм умножения матриц Штрассена на C и заставил его работать правильно. Однако способ, которым я передаю подматрицы в каждой рекурсии, далек от оптимального, поскольку я создаю новый массив и копирую элементы из исходной матрицы. Вот моя реализация

// this algorithm assumes that both matrices have the same size and are square matrices.
int **matrix_multiply_divide_conquer(const int **A, const int **B, int length, int threshold)
{
  int **result;
  int i, j, k;
  // allocate result space
  result = (int **)malloc(sizeof(int *) * length);
  for (i = 0; i < length; i++)
  {
    result[i] = (int *)malloc(sizeof(int) * length);
  }

  if (length == threshold)
  {
    // compute the dot product
    matrix_multiply((const int **)A, (const int **)B, result, length, length, length, false);
    return result;
  }
  else
  {
    // stored in an int given that the matrix length is guaranteed to be a power of 2
    int nLength = length / 2;
    int i;
    int **a11;
    int **a12;
    int **a21;
    int **a22;

    int **b11;
    int **b12;
    int **b21;
    int **b22;

    // allocate new sub matrices
    a11 = (int **)malloc(sizeof(int *) * nLength);
    a12 = (int **)malloc(sizeof(int *) * nLength);
    a21 = (int **)malloc(sizeof(int *) * nLength);
    a22 = (int **)malloc(sizeof(int *) * nLength);

    b11 = (int **)malloc(sizeof(int *) * nLength);
    b12 = (int **)malloc(sizeof(int *) * nLength);
    b21 = (int **)malloc(sizeof(int *) * nLength);
    b22 = (int **)malloc(sizeof(int *) * nLength);

    for (i = 0; i < nLength; i++)
    {
      a11[i] = (int *)malloc(sizeof(int) * nLength);
      a12[i] = (int *)malloc(sizeof(int) * nLength);
      a21[i] = (int *)malloc(sizeof(int) * nLength);
      a22[i] = (int *)malloc(sizeof(int) * nLength);

      b11[i] = (int *)malloc(sizeof(int) * nLength);
      b12[i] = (int *)malloc(sizeof(int) * nLength);
      b21[i] = (int *)malloc(sizeof(int) * nLength);
      b22[i] = (int *)malloc(sizeof(int) * nLength);
    }

    a11 = get_sub_matrix((const int **)A, 0, 0, nLength);
    a12 = get_sub_matrix((const int **)A, 0, nLength, nLength);
    a21 = get_sub_matrix((const int **)A, nLength, 0, nLength);
    a22 = get_sub_matrix((const int **)A, nLength, nLength, nLength);


    b11 = get_sub_matrix((const int **)B, 0, 0, nLength);
    b12 = get_sub_matrix((const int **)B, 0, nLength, nLength);
    b21 = get_sub_matrix((const int **)B, nLength, 0, nLength);
    b22 = get_sub_matrix((const int **)B, nLength, nLength, nLength);

    // combine the results
    int **c11 = matrix_addition((const int **)matrix_multiply_divide_conquer((const int **)a11, (const int **)b11, nLength, 4), (const int **)matrix_multiply_divide_conquer((const int **)a12, (const int **)b21, nLength, 4), nLength, nLength);
    int **c12 = matrix_addition((const int **)matrix_multiply_divide_conquer((const int **)a11, (const int **)b12, nLength, 4), (const int **)matrix_multiply_divide_conquer((const int **)a12, (const int **)b22, nLength, 4), nLength, nLength);
    int **c21 = matrix_addition((const int **)matrix_multiply_divide_conquer((const int **)a21, (const int **)b11, nLength, 4), (const int **)matrix_multiply_divide_conquer((const int **)a22, (const int **)b21, nLength, 4), nLength, nLength);
    int **c22 = matrix_addition((const int **)matrix_multiply_divide_conquer((const int **)a21, (const int **)b12, nLength, 4), (const int **)matrix_multiply_divide_conquer((const int **)a22, (const int **)b22, nLength, 4), nLength, nLength);

    // combine result quarters
    combine_sub_matrix((const int **)c11, result, nLength, 0, 0);
    combine_sub_matrix((const int **)c12, result, nLength, 0, nLength);
    combine_sub_matrix((const int **)c21, result, nLength, nLength, 0);
    combine_sub_matrix((const int **)c22, result, nLength, nLength, nLength);
    return result;
  }
}

это метод get_sub_matrix:

int **get_sub_matrix(const int **A, int verticalOffset, int horizontalOffset, int size)
{
  int **sub_matrix;
  sub_matrix = (int **)malloc(sizeof(int *) * size);
  int i, j;
  for (i = 0; i < size; i++)
  {
    //each row will contain a number of columns size
    sub_matrix[i] = (int *)malloc(sizeof(int) * size);
  }
  for (i = 0; i < size; i++)
  {
    for (j = 0; j < size; j++)
    {
      sub_matrix[i][j] = A[i + verticalOffset][j + horizontalOffset];
    }
  }
  return sub_matrix;
}

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

Я пробовал следующее, но это не сработало:

int **a11 = &A[0][0];
int **a12 = &A[0][nLength];
int **a21 = &A[nLength][0] ;
int **a22 = &A[nLength][nLength];

int **b11 = &B[0][0];
int **b12 = &B[0][nLength];
int **b21 = &B[nLength][0] ;
int **b22 = &B[nLength][nLength];

Спасибо, что помогли мне.

# matrix-multiplication
Источник
Codelisting
за 0 против

Теперь вы работаете с массивом строк,

 int **x = malloc(sizeof(int *) * size);

а затем вы выделяете память для каждой строки.

for (i = 0; i < length; i++)
{
    x[i] = malloc(sizeof(int) * length);
}

Вместо этого вы можете работать с одним блоком памяти, который вы рассматриваете как двумерный массив:

int *x = malloc(sizeof(int) * size * size);

Это позволяет вам указать на начало подматрицы и передать его другим функциям. Но обратите внимание, как вы должны выполнять индексацию матрицы. Поскольку компилятор теперь не знает, что вы обрабатываете отдельный блок как 2-мерный массив, вы должны явно выполнить индексацию самостоятельно. Итак, учитывая матрицу размераlength кlength вы обращаетесьx[2][3] (четвертый элемент третьей строки, поскольку C отсчитывается от нуля) как:

x [ (2*length) + 3 ];

Кроме того, при передаче указателей на подматрицы в ваши функции вы должны разработать соглашение, чтобы сообщить вашим функциям, с какой подматрицей они работают. Например:

void my_matrix_op(int *X, int quadrant, int length)

Я не просматривал весь ваш код, чтобы определить, действительно ли этот подход применим для вашего алгоритма, но я надеюсь, что это вам поможет.

Codelisting
Популярные категории
На заметку программисту