一定時間に行列を分割する

Question

StrassenのアルゴリズムをC++の行列乗算に実装しようとしていますが、2つの行列をそれぞれ4つの部分に一定時間で分割する方法を見つけたいと思います。ここで私はそうやっている現在の方法は次のとおりです。

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を追加し、N ^コール。

これを行う方法は、値をコピーするのではなく、4つの部分行列へのポインタを作成することですが、ポインタの作成方法を理解するのは困難です。どんな助けもありがとう。

Answer 1

マトリックスを考えないで、マトリックスビューを考えてみましょう。

マトリックスビューには、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のではなく、行列に動作しません。

Answer 2

使用する小さなマトリックスの親マトリックスの位置を保持するサブマトリックスクラスを作成することができます。行と列の開始インデックスを保存しておき、それらのオフセットによってインデックスをオフセットする必要がある場合を除いて、ほとんどあなたが既にMatrixで持っているものだけです。正しく実行された場合、メイン/ルートマトリックスは、完全マトリックスを境界として持つサブマトリックスになります。