压缩稀疏行转置

Question

如您所知，我们可以使用压缩行存储（CRS）（或者压缩稀疏行（CSR））来编写稀疏矩阵。 假设A是一个m×n的矩阵，则其转置A'是一个n×m的矩阵，对于所有0 <= i < n和0 <= j < m，A'(i; j) = A(j; i)。

我需要编写CRS表示法下矩阵转置的算法。我该如何解决这个问题？

- qwers

Answer 1

我正在寻找类似的东西。这是我的算法。我不知道它是否是最快的，但我认为它相当不错。

编辑：基本上相同的算法在scipy的C++模块中实现。

假设矩阵由这个结构体表示：

struct CRSMatrix
{
    int n; // number of rows
    int m; // number of columns
    int nz; // number of non-zero elements
    std::vector<double> val; // non-zero elements
    std::vector<int> colIndex; // column indices
    std::vector<int> rowPtr; // row ptr
};

这个函数执行它：

CRSMatrix sparse_transpose(const CRSMatrix& input) {
    CRSMatrix res{
        input.m,
        input.n,
        input.nz,
        std::vector<double>(input.nz, 0.0),
        std::vector<int>(input.nz, 0),
        std::vector<int>(input.m + 2, 0) // one extra
    };

    // count per column
    for (int i = 0; i < input.nz; ++i) {
        ++res.rowPtr[input.colIndex[i] + 2];
    }

    // from count per column generate new rowPtr (but shifted)
    for (int i = 2; i < res.rowPtr.size(); ++i) {
        // create incremental sum
        res.rowPtr[i] += res.rowPtr[i - 1];
    }

    // perform the main part
    for (int i = 0; i < input.n; ++i) {
        for (int j = input.rowPtr[i]; j < input.rowPtr[i + 1]; ++j) {
            // calculate index to transposed matrix at which we should place current element, and at the same time build final rowPtr
            const int new_index = res.rowPtr[input.colIndex[j] + 1]++;
            res.val[new_index] = input.val[j];
            res.colIndex[new_index] = i;
        }
    }
    res.rowPtr.pop_back(); // pop that one extra

    return res;
}

- Marko

---

对于那些试图理解res.rowPtr是什么的人来说：你需要一个数据结构来回答一个简单的查询问题“在这个元素之前有多少个元素被放置了？”，所以如果你仔细观察res.rowPtr，你会发现对于colIndex[i]（转置后的行索引），答案被放置在colIndex[I]+1中。而res.rowPtr.pop_back();可以在主循环之前出现。 - undefined

SysEng 在此帖子中提问道：我注意到上面的答案在转置后没有更新m和n的维度。这两个应该是不同的吧？ - undefined

@dbc，我没明白你的问题。你是什么意思？你是在指这个在SO上的确切问题，还是说你弄错了，实际上想链接到另一个问题？此外，我不知道为什么你提到SysEng？至于这个答案，我可以说在转置的最开始，我确实会交换m和n维度。 - undefined

@Marko - 我所提到的帖子在审核过程中被删除了。虽然如此，我认为那是一个有效的评论，所以我在这里重新发表了它，并标明了来源。 - undefined