graph - 压缩稀疏行(CSR)稀疏矩阵的快速访问元素

Question

我想测试一些较新的稀疏线性求解器，并且想知道是否存在快速填充矩阵的方法。我感兴趣的格式是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值，这意味着它们需要被添加

提前致谢!

Answer 1

您拥有的就是所谓的三元组稀疏格式。可以非常有效地实现CRS的创建，包括删除重复的条目和对值求和。在自己编程之前，请查看SuiteSparse library。它是用C编写的，但是我相信您会理解它的原理。您感兴趣的是cholmod_triplet.c文件，该文件实现了所需的功能。

本质上，转换是对行和列索引使用两阶段存储桶排序来执行的。该算法具有线性复杂度，如果您对处理大型数据集感兴趣，这很重要。

编辑如果要一起跳过三元组格式的显式创建，则可以通过动态生成(row, col)连接并将其添加到动态稀疏结构中来实现。我通常使用插入排序和排序列表来执行此操作，这实际上是最快的。它也比将三元组转换为CRS更快，并且使用的内存更少。该方法如下:

(如果您大概知道的话)，每行中有多少个非零条目，为每行预分配一个(空)列索引数组，以及一个单独的值数组(不是链接列表，而是一个简单数组) )的大小。就像是
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中。这是缓存友好的，因为实际上行很小，足以容纳当今的任何缓存。

完成后，您需要通过将单个行列表复制到最终的columns中，将单个排序列表组装为有效的CRS结构。与值相同。

如果可以确定某些行的条目可以为零，则实际上可以通过预分配静态“列表数组”来避免最后一步。因此，每行条目数将保持不变，其中某些条目可能为零。有时候没关系。

这种方法比使用三重态到稀疏转换更快，至少对于我使用的FEM模型而言。通常的原因是内存带宽是这里的瓶颈，而以上方案使用的内存要少得多:

创建三元组格式需要花费时间，并且您需要将三元组写入内存中

转换为CRS要求至少读取和写入三元组以对其进行排序(如果您查看算法，则实际上要多于一次。要进行两次排序，并且需要辅助数据结构。)

(取决于连接结构)，您可能最终会拥有大量的三元组格式的(row, col)重复项，这些重复项在组装过程中会通过添加相应的值来删除。上述方法不存在这种开销-如果行列表中已经存在col，则只需更新相应的值即可。

如果您将行范围分配给各个工作程序，则可以并行完成

更新排序列表。无需通信，也不需要同步。确保负载平衡是另一回事...

看看a performance comparison of using those two methods (Figure 1)在2D中的三角形元素。请注意，性能差异取决于三元组中的条目数与组合后的稀疏矩阵格式的比率(表2)。但一般而言，该方法绝不会比从三元组到crs转换差，和三元组需要首先创建。您还可以下载MATLAB MEX函数sparse_create，它是mutils软件包的一部分(请参见下载部分)。