Разбиение матрицы за постоянное время

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

for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
        A11[i][j] = a[i][j];
        A12[i][j] = a[i][j+n];
        A21[i][j] = a[i+n][j];
        A22[i][j] = a[i+n][j+n];
        B11[i][j] = b[i][j];
        B12[i][j] = b[i][j+n];
        B21[i][j] = b[i+n][j];
        B22[i][j] = b[i+n][j+n];
    }
}

Этот подход, очевидно, O (n ^ 2), и он добавляет n ^ 2 * log (n) к среде выполнения, поскольку он вызывается для каждого рекурсивного вызова.

Кажется, что способ сделать это в постоянное время состоит в том, чтобы создать указатели на четыре подматрицы, а не копировать значения, но мне трудно понять, как создавать эти указатели. Любая помощь будет оценена по достоинству.


c++ matrix matrix-multiplication c++11 strassen
person user3483203    schedule 29.11.2016    source источник
comment
Ваша исходная матрица имеет размер 2*n?   -  person Pavel    schedule 29.11.2016

Ответы (2)


arrow_upward
1
arrow_downward

Не думайте о матрицах, думайте о матричных представлениях.

Матричное представление имеет указатель на буфер T, ширину, высоту, смещение и шаг между столбцами (или строками).

Мы можем начать с типа представления массива.

template<class T>
struct array_view {
  T* b = 0; T* e = 0;
  T* begin() const{ return b; }
  T* end() const{ return e; }

  array_view( T* s, T* f ):b(s), e(f) {}
  array_view( T* s, std::size_t l ):array_view(s, s+l) {}

  std::size_t size() const { return end()-begin(); }
  T& operator[]( std::size_t n ) const { return *(begin()+n); }
  array_view slice( std::size_t start, std::size_t length ) const {
    start = (std::min)(start, size());
    length = (std::min)(size()-start, length);
    return {b+start, length};
  }
};

Теперь наш матричный вид:

temlpate<class T>
struct matrix_view {
  std::size_t height, width;
  std::size_t offset, stride;
  array_view<T> buffer;

  // TODO: Ctors
  // one from a matrix that has offset and stirde set to 0.
  // another that lets you create a sub-matrix
  array_view<T> operator[]( std::size_t n ) const {
    return buffer.slice( offset+stride*n, width ); // or width, depending on if row or column major
  }
};

Теперь ваш код работает с matrix_views, а не с матрицами.

person Yakk - Adam Nevraumont    schedule 29.11.2016

arrow_upward
0
arrow_downward

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

person 1201ProgramAlarm    schedule 29.11.2016