使用对的矩阵乘法

Question

我正在研究进行矩阵乘法的替代方法。我没有将矩阵存储为二维数组，而是使用向量来

vector<pair<pair<int,int >,int > > 

存储矩阵。我的对 (pair) 中的对存储我的索引 (i,j)，另一个 int 存储给定 (i,j) 对的值。我想我可能会幸运地以这种方式实现我的稀疏数组。

问题是当我尝试将该矩阵与其自身相乘时。

如果这是一个二维数组实现，我会按如下方式乘以矩阵：

   for(i=0; i<row1; i++)
    {
        for(j=0; j<col1; j++)
        {
          C[i][j] = 0;
         for(k=0; k<col2; k++) 
           C[i][j] += A[i][j] * A[j][k];
      }
    }

有人可以指出一种使用我的“对对”向量实现相同结果的方法吗？

谢谢

Answer 1

到目前为止，您可以在一个位置存储一个值。如果要在矩阵中存储多个非零条目，则需要在更大的结构中添加更多对。

map, int> 将是下一个逻辑步骤。现在您可以迭代行，因为first 坐标在map 的排序顺序中更重要。

要迭代列，请颠倒该优先级：

typedef pair<int, int> mx_coord;
struct reverse_compare {
    bool operator() (mx_coord const &l, mx_coord const &r) const
        { return l.second < r.second? true :
                 r.second < l.second? false : l.first < r.first; }
};

typedef map< mx_coord, int > matrix;
typedef map< mx_coord, int, reverse_compare > matrix_transpose;

要将 A 乘以 B，请转置 B 并迭代 A 和 B，将不太重要的坐标匹配的任何元素相乘，因为顺序自然允许您逐行和逐列进行-柱子。

转置 B：

matrix_transpose b_t( b.begin(), b.end() ); // complexity: n log n