压缩稀疏行（CSR）稀疏矩阵中元素的快速访问

Question

压缩稀疏行（CSR）稀疏矩阵中元素的快速访问

4

我想测试一些最新的稀疏线性求解器，想知道是否有一种快速填充矩阵的方法。我感兴趣的格式是CSR（http://goo.gl/hLXYd）。假设矩阵以CSR格式给出：

values(num non-zero elements)
columns(num non-zero elements)
rowIndex(num rows + 1)

考虑到这是从网络中导出的稀疏矩阵。所以，我有成千上万的节点，其中一些通过线连接在一起。因此，该矩阵在结构上是对称的。每个连接(i,j)都会对对角线项(i,i)和(j,j)以及非对角线项(i,j)和(j,i)添加一些内容。我可能会在相同的节点之间有几个连接(i,j,1)，(i,j,2)...所以，我可能需要多次重新访问2个对角线和2个非对角线元素。

我知道可以通过执行rowIndex(i)来获取行的开头。然后，我将需要遍历元素列(rowIndex(i):rowIndex(i+1)-1)以查找j位于哪里。

问题：

在CSR格式下，是否有一种更快地访问元素的方法，而无需每次更新元素时进行搜索？

一些澄清：我只需要从头开始填充矩阵。该矩阵在结构上是对称的，但实际上并不对称。保存的值与网络数据（阻抗、电阻等）有关，它们具有实际值。通常情况下，Value(i,j)<>Value(j,i)。我有形式为(name1,i1,j1,value1),(name2,i2,j2,value2)等的元组。这些元组未排序，并且2个元组可能引用相同的i,j值，这意味着它们需要相加

提前感谢！

- electrique

2个回答

1

你的问题似乎混淆了两个不同的问题：

以CSR格式快速创建矩阵的方法是什么？
是否有一种更快的方法从已经存储在CSR格式中的矩阵中读取值？（比你描述的直接方法更快）

所以这里有两个答案：

通常情况下，将网络数据从任何形式读入到类似于键字典的结构中（其他中间形式也可用且可能更适合您的速度或其他原因），然后将该中间结构转换为矩阵的CSR格式。以下是更多信息。
我不认为有，对于以CSR格式存储的矩阵来说，访问相对较慢是为节省空间而付出的代价之一。你已经用时间换取了空间，或者用空间换取了时间，这取决于你的观点。

根据您对输入数据的描述，建议您考虑设计自己的中间形式来整理原始数据。由于您的邻接矩阵是对称的，因此您只需要以任何形式存储其中一半。此外，您可能不需要存储主对角线上的元素--我猜测节点i始终连接到节点i或从未连接，因此网络的特性决定了存储在(i,i)处的值。我对您要存储在矩阵每个节点上的信息还有一点不确定，是关于i和j之间连接数量还是其他内容？

- High Performance Mark

对于混淆我感到抱歉，我不需要（2）。我只需要从头开始填写矩阵。矩阵在结构上对称而不是真正的对称。保存的值与网络数据有关（阻抗，电阻等），它们是实际值。通常情况下，Value（i，j）<> Value（j，i）。我有形式为（name1，i1，j1，value1），（name2，i2，j2，value2）等的元组。这些元组未排序，2个元组可以引用相同的i，j值，这意味着它们需要添加。希望我没有让您更加困惑。 - electrique

我经常在SO上感到困惑，不用担心，但请编辑您的问题，以便下一个路过的人能更清楚地了解您想要什么。 - High Performance Mark

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- angainor · Accepted Answer

你所拥有的是所谓的三元稀疏格式。创建CRS，包括删除重复条目和求和值，可以非常高效地实现。在编写程序之前，请查看SuiteSparse库。它是用C写的，但我相信你会理解其原理。你需要关注的是cholmod_triplet.c文件，它实现了你需要的功能。

基本上，转换是使用行和列索引的两阶段桶排序来执行的。如果您想处理大型数据集，则此算法具有线性复杂度，这很重要。编辑如果您想完全跳过显式创建三元组格式，则可以通过在运行时生成(row, col)连接并将其添加到动态稀疏结构中来完成。我通常使用插入排序和排序列表来完成这项工作，这在实践中是最快的。它也比三元组转换更快，并且使用的内存要少得多。该方法的步骤如下：

如果您大致知道每行有多少个非零条目，则为每行预先分配一个(空)列索引数组和一个单独的值数组(不是链接列表，而是一个简单的数组)，例如：

static_lists_cols[row] = malloc(sizeof(int)*expected_number_of_non_zeros) static_lists_vals[row] = malloc(sizeof(double)*expected_number_of_non_zeros)
如果您不知道，则选择一个初始大小，并在行列表已满时根据需要进行重新分配(使用一些块大小足够大以避免重新分配开销)。
对于每个(row, col)对，使用插入排序将col插入到对应于row的排序列表中。对于小型(最多几百个)非零元素每行，线性搜索是最快的。对于每行有更多非零元素的情况，您可以使用二分法来定位正确的插入col索引的位置。
col通过移动在排序列表中具有较高列索引的非零条目来插入到第row个排序列表中。这是缓存友好的，因为现今实际上所有行都足够小，可以适合任何缓存。
完成后，您需要将单独的排序列表组装成有效的CRS结构，方法是将单独的行列表复制到最终的columns中。值也一样。
如果您没有关系某些行可能会有零项，则实际上可以通过预先分配静态“列表数组”来避免最后一步。因此，每行将有恒定数量的条目，其中一些可能是零。有时这样做是可以接受的。

这种方法比使用三元组转换为稀疏格式更快，至少对于我使用的FEM模型而言。一般的原因是内存带宽在这里成为瓶颈，而上述方案使用的内存要少得多：

创建三元组格式需要时间，并且需要将三元组写入内存
转换为CRS需要至少读取和写入三元组一次以进行排序(实际上比一次多一点，如果你看算法。你需要排序两次，并且需要辅助数据结构。)
根据连通性结构的不同，你可能会在三元组格式中有大量的(row,col)重复项，在装配过程中通过添加相应的值来删除这些重复项。该开销在上面的方法中不存在- 如果col已经存在于行列表中，则只需更新相应的值即可。
如果将行范围分配给单个工作者，可以并行地更新排序后的列表。不需要通信或同步。确保负载平衡是另外一件事...

请查看在2D三角形元素中使用这两种方法的性能比较（图1）。请注意，性能差异取决于三元组中的条目数与装配后的稀疏矩阵格式的比率（表2）。但总的来说，该方法永远不会比三元组转换为CRS更差，而且首先需要创建三元组。您还可以下载MATLAB MEX函数sparse_create，这是mutils包的一部分（请参见下载部分）。