转置修改后的 CSR 格式 (C++)

Question

我正在尝试转置以修改后的 CSR 格式编写的矩阵（GF(2) 字段，因此无需存储元素）：

class GF2_CSR_Matrix
{
protected:
    uint64_t rows;
    uint64_t columns;
    uint64_t non_zero;
    std::vector<uint64_t> nonzeros_per_row; (Here each element is only number of NZ in row, unlike classical CSR which stores total NZ in rows before)
    std::vector<uint64_t> column_indexes; (idx of columns containing NZ)
}

我还有并行函数来计算部分和。

void calculate_prefix_sum(std::vector<std::pair<uint64_t, uint64_t>> &j_ends,
                          const std::vector<uint64_t> &nonzeros_per_row) // .first is start of indexing, .second is end. In fact [i].second equals [i+1].first

有人可以帮助我吗？

Answer 1

沿着这些思路（未测试）：

std::vector<uint64_t> nonzeros_per_column(columns, 0);
for (uint64_t col : column_indexes) {
  ++nonzeros_per_column[col];
}

// Count of non-zero elements in all columns to the left of `col`.
std::vector<uint64_t> cumulative_nonzeros_per_column;
cumulative_nonzeros_per_column.reserve(columns);
cumulative_nonzeros_per_column.push_back(0);
for (uint64_t col = 1; col < columns; ++col) {
  cumulative_nonzeros_per_column.push_back(
    cumulative_nonzeros_per_column.back() + nonzeros_per_column[col];
}

std::vector<uint64_t> row_indexes(non_zero);
// Need another set of counters for the final pass.
std::vector<uint64_t> temp_nonzeros_per_column(columns, 0);
uint64_t row = 0;
uint64_t nz_in_row = 0;
for (uint64_t col : column_indexes) {
  for (;;) {
    if (++nz_in_row <= nonzeros_per_row[row]) break;
    ++row;
    nz_in_row = 0;
  }
  // How many non-zero elements would precede this element in column-wise
  // traversal? The cumulative count in all columns to the left, plus the
  // count encountered so far in the current column.
  row_indexes[cumulative_nonzeros_per_column[col] +
              temp_nonzeros_per_column[col]++] = row;
  
}

// row_indexes becomes column_indexes of the transposed matrix
// nonzeros_per_row becomes nonzeros_per_column of the transposed matrix