"Splitting" 恒定时间的矩阵

Question

我正在尝试在 C++ 中实现 Strassen 的矩阵乘法算法，并且我想找到一种方法在常数时间内将两个矩阵分成四个部分。这是我目前这样做的方式：

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) 添加到运行时，因为每次递归调用都会调用它。

似乎在恒定时间内执行此操作的方法是创建指向四个子矩阵的指针，而不是复制值，但我很难弄清楚如何创建这些指针。任何帮助将不胜感激。

Answer 1

您可以创建一个子矩阵 class 来保存您要使用的较小矩阵在父矩阵中的位置。主要是您已经拥有的矩阵，除了您需要存储行和列的起始索引，然后用这些偏移量偏移您的索引。如果操作正确，main/root 矩阵将是一个以完整矩阵为边界的子矩阵。

Answer 2

不要考虑矩阵，考虑矩阵视图。

矩阵视图具有指向 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_view 上工作，而不是矩阵。

"Splitting" 恒定时间的矩阵

"Splitting" a matrix in constant time

c++

matrix

matrix-multiplication

strassen

c++11