在同一时间内“分割”一个矩阵

我想在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）的运行时间，因为它是所谓的每个递归呼叫。

似乎在常量时间这样做的方式是创建指向四个子矩阵的指针，而不是复制值，但我很难找出如何创建这些指针。任何帮助，将不胜感激。

来源

2016-11-29 chrisz

你的源矩阵的大小是2 * n吗？ – Pavel

不要想到矩阵，想到矩阵的意见。

矩阵视图具有指向缓冲区的指针，其宽度，高度，偏移量和列（或行）之间的跨度为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 S，不是矩阵的工作。

来源

2016-11-29 16:52:25 Yakk

正是我在找的，谢谢！ – chrisz

您可以创建一个子矩阵类来保存要使用的较小矩阵的父矩阵中的位置。大多数情况下，您已经拥有了矩阵，除了需要存储行和列的起始索引，然后通过偏移索引来抵消索引。如果正确完成，主/根矩阵将是以完整矩阵作为边界的子矩阵。

来源

2016-11-29 16:44:33 1201ProgramAlarm

在同一时间内“分割”一个矩阵

回答

相关问题