2

我有一个非对称的稀疏矩阵 IE 稀疏度有点随机，我不能指望所有值都与对角线相距一定距离。

但是，它仍然是稀疏的，我想减少对矩阵的存储需求。因此，我试图弄清楚如何存储从第一个非零开始的每一行，直到我到达最后一个非零。

也就是说，如果第 m 行的第一个非零出现在第 2 列，最后一个非零出现在第 89 列，我想存储在 A[m] 行 2-> 89 中。

由于每一行没有相同数量的非零，我将使 A 的所有行都具有相同数量的元素，并将零填充到具有较少数量非零元素的行的行尾.

我如何在 C 中进行此翻译？我实际上没有原始的完整矩阵来复制值（原始矩阵以 CSR 形式出现在我身边）。如果我在 fortran 中执行此操作，我可以将我的数组定义为二维的，并且通过跟踪非零列的开始/停止值并像这样存储它，让每一行都是可变长度的。

我将尝试在下面演示：

这是我知道的值的矩阵表示 - 对于每个值，我知道行和列的位置

  [1    2    3    4                   ]
  [   5    6    7    8                ]
  [       10    11    12    13        ]
 m[   14    15    16    17       18   ]
  [         19    20    21         22 ]

现在这一行在m第一个非零和最后一个非零之间具有最大的“跨度”，所以我的新矩阵将是5x[span of row m]

  [1     2     3     4          ]
  [5     6     7     8          ]
  [10    11    12    13         ]
 m[14    15    16    17       18]
  [19    20    21       22      ]

如您所见，行m不需要零填充，因为它是最长的“跨度”

其他行现在都将零行作为第一个非零，并在每个非零之间保持零列的间距。

4

3 回答 3

3

我会将其实现为一个参差不齐的数组，其中 A[n][0] 始终返回对角线上的元素。A[n][1] 将返回对角线右侧的项目， A[n][2] 将返回对角线左侧的项目，依此类推。然后，您只需要一个将矩阵索引 [i,j] 映射到不规则数组索引 [r][s] 的函数。

这具有稀疏性的优点，如果您的值靠近对角线，则数组不会很长。

或者，您可以有以下定义：

struct Row
{
    int InitialOffset;
    int NumElements;
    int[] Values;
}

然后你会有一个 Row[]。根据矩阵索引检索值如下所示：

//matrix is merely an array of rows...
int GetValue(*matrix this, int i, int j)
{
    Row CurrentRow = (*this)[i];
    if (CurrentRow.InitialOffset > j)
        return 0;
    else if (CurrentRow.InitialOffset + CurrentRow.NumElements < j)
        return 0; 
    return CurrentRow.Values[j - CurrentRow.InitialOffset]
}

我的 C 语法有点模糊，但你应该明白了。

根据您的演示，我建议这样做：

struct Matrix
{
    int[,] Data
    int[] StartOffset;
    int[] NumberElements;
}

如下使用...

int GetValue(*Matrix this, int i, int j)
{
    if (this.StartOffset[i] > j)
        return 0;
    else if (this.StartOffset[i] + this.NumberElements[i] < j)
        return 0; 
    return this.Data[i, j-this.StartOffset[i]];
}

您的初始化过程看起来像这样

//Data is a struct that holds row index, col index, and value
Matrix* InitMatrix (*Data values, int numVals)
{
    //loop through values to find longest row and number of rows
    //create new matrix, malloc matrix for longrow * numRows
    //malloc numrows elements for StartOffset and NumItems
    //foreach row, find min() and max()-min() of col indexs and 
    //store in StartOffset and NumItems
}

您需要进行一些处理，但数据压缩并不便宜。

于 2010-08-12T18:53:24.917 回答
2

另一种方法是使用链接结构（如果矩阵非常稀疏，则非常有效，而不是因为填充得更多）。我在较早的答案中暗示了实施。

我将使用连续运行实现，我不确定您是否真的想要/需要使用相等长度的行。为什么不使用参差不齐的数组？

于 2010-08-12T18:49:12.310 回答
1

Derek，您在其中一个评论中提到要使用单个 malloc。这意味着你知道你有多少非空元素。鉴于此， tt 可以将稀疏矩阵存储在一个数组中，该数组包含每个元素的矩阵元素的值和到下一个元素的“位置增量”。就像是：

struct melem {
    int value; // value of data
    int offset; // offset to next element
}

struct melem matrix[num_nonempty_elements];

...

// Note: this is pseudocode!
matrix[row*COLS + col].value = a[row][col];
matrix[row*COLS + col].offset = (row*COLS + col)_[i] - (row*COLS + col)_[i-1];

编辑：考虑一下，这与链表方法非常相似，但需要 1 次分配。OTOH，可能需要更多计算才能访问所需的单元格。

于 2010-08-12T19:32:16.973 回答