algorithm - 如何将压缩行存储转换为稀疏矩阵的压缩列存储？

Question

我有一个相对较大(例如，5000 行乘 8000 列)的稀疏矩阵，存储在 compressed row storage 中(CRS)。我正在尝试获取它的 compressed column storage (CCS) 表格。

是否已经有执行此操作的标准算法？一种选择是从 CRS 重建整个矩阵(4000 万个条目)，然后使用简单的算法获得其 CCS。然而，这样做的时间复杂度太高了，我计划在更大的矩阵上使用这个算法。关于如何做到这一点还有其他想法吗？

Answer 1

可能不如数字食谱代码有效，但我想出了这个似乎可行的方法:

#include <stdio.h>
#include <string.h>

#define COLS 6
#define SIZE(a) (sizeof(a)/sizeof(*(a)))

int main() {
  float f[] = {10,-2, 3, 9, 3, 7, 8, 7, 3, 8, 7, 5, 8, 9, 9,13, 4, 2, 1};
  int   c[] = { 0, 4, 0, 1, 5, 1, 2, 3, 0, 2, 3, 4, 1, 3, 4, 5, 1, 4, 5};
  int   r[] = { 0,    2,       5,       8,         12,         16,       19};
  float nf[SIZE(f)];
  int   nc[COLS+1] = {0};
  int   nr[SIZE(f)];
  int   nn[COLS+1];

  int rr[SIZE(f)];
  for (int k = 0, i = 0; i < SIZE(r); i++)
    for (int j = 0; j < r[i+1] - r[i]; j++)
      rr[k++] = i;

  for (int i = 0; i < SIZE(f); i++)
    nc[c[i]+1]++;
  for (int i = 1; i <= COLS; i++)
    nc[i] += nc[i-1];
  memcpy(nn, nc, sizeof(nc));

  for (int i = 0; i < SIZE(f); i++) {
    int x = nn[c[i]]++;
    nf[x] = f[i];
    nr[x] = rr[i];
  }

  for (int i = 0; i < SIZE(nf); i++) printf("%2.0f ", nf[i]);
  putchar('\n');
  for (int i = 0; i < SIZE(nr); i++) printf("%2d ", nr[i]);
  putchar('\n');
  for (int i = 0; i < SIZE(nc); i++) printf("%2d ", nc[i]);
  putchar('\n');

  return 0;
}